leetcode - 1026. Maximum Difference Between Node and Ancestor

Given the root of a binary tree, find the maximum value v for which there exist different nodes a and b where v = |a.val - b.val| and a is an ancestor of b.

A node a is an ancestor of b if either: any child of a is equal to b or any child of a is an ancestor of b.

 

Example 1:

Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
Explanation: We have various ancestor-node differences, some of which are given below :
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.

문제 : 이진트리에서  | 부모노드값-자식노드값 |(절대값) 의 최대값을 구해라.

 

풀이 : BFS 활용

1. 루트노드부터 왼쪽으로 탐색하여 최대 절대값을 구한다.

2. 루트노드부터 오른쪽으로 탐색하여 최대 절대값을 구한다. 

3. 왼쪽, 오른쪽의 최대 절대값 리턴한다.

class Solution {
    public int maxAncestorDiff(TreeNode root) {
        
        //최대,최소 초기화
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        
        int res = maxAncestorDiff(root, min, max);
        return res;
    }
    
    public int maxAncestorDiff(TreeNode root, int min, int max) {
        
        if(root == null) return Math.abs(max-min);
        //최소,최대 갱신
        max = Math.max(max,root.val);
        min = Math.min(min,root.val);
        int lMax = maxAncestorDiff(root.left, min, max);
        int rMax = maxAncestorDiff(root.right, min, max);
        
        return Math.max(lMax,rMax);
    }
}

 

leetcode 풀이

class Solution {
    int res = 0;
    public int maxAncestorDiff(TreeNode root) {
        dfs(root, root.val, root.val);
        return res;
    }
    
    void dfs(TreeNode node, int min, int max) {
        if(node == null)
            return;
        
        //노드의 최대,최소 갱신
        min = Math.min(min, node.val);
        max = Math.max(node.val, max);
        
        //절대값 최댓값 갱신
        res = Math.max(res, max-min);
        
        dfs(node.left, min, max);//왼쪽노드탐색
        dfs(node.right, min, max);//오른쪽노드탐색
    }
}