[Leetcode][Java]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.

 

이진트리의 루트가 주어진다. V의 최댓값을 구해라 

A가 B의 조상인 경우에 V = |A.val - B.val| 

A가 B의 조상이라고 말하는 경우는 아래와 같다

A의 어떠한 자식이 B와 같은 경우 거나, A의 어떠한 자식이든 B의 선조인 경우이다. 

( 쉽게 말해, 이진트리에 존재하는 노드의 값들 중 노드의 값의 차가 최댓값인 것을 구해라 ) 

---

dfs를 이용해서 해답을 구해보자.

노드를 방문하며, 지금까지 구한 min, max값을 파라미터로 넘기고 

현재 방문한 노드의 값이 min, max값에 해당하는지 비교하여 값을 업데이트 한 후에 

min과 max의 차를 result로 저장하면 된다.

    private void dfs(TreeNode node, int min, int max) {
        min = Math.min(node.val, min);
        max = Math.max(node.val, max);

        rst = Math.max(rst, max -min);

        if (node.right != null) {
            dfs(node.right, min, max);
        }

        if (node.left != null) {
            dfs (node.left, min, max);
        }
    }

해당 메소드를 호출하는 부분을 보자.

결과 값은 전역변수로 선언하였다.

    int rst = 0;
    public int maxAncestorDiff(TreeNode root) {
        
        if (root != null) {
            dfs (root, root.val, root.val);
        }
        return rst;
    }

전역 변수를 사용하지 않는 경우에는 result가 되는 값을 파라미터로 넘기면 된다.

    public int maxAncestorDiff(TreeNode root) {
        
        int rst = 0;
        if (root != null) {
            rst = dfs (root, root.val, root.val, 0);
        }
        return rst;
    }

    private int dfs(TreeNode node, int max, int min, int rst) {

        min = Math.min(node.val, min);
        max = Math.max(node.val, max);

        rst = Math.max(rst, max -min);
        int right = rst;
        if (node.right != null) {
            right = dfs(node.right, max, min,rst);
        }

        int left = rst;
        if (node.left != null) {
            left = dfs (node.left, max, min, rst);
        }

        return Math.max(left, right);
    }

 

문제 출처

leetcode.com/problems/maximum-difference-between-node-and-ancestor/

Maximum Difference Between Node and Ancestor - LeetCode