1026. Maximum Difference Between Node and Ancestor

문제

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

풀이

class Solution {
    int answer = 0;
    public int maxAncestorDiff(TreeNode root) {
        DFS(root, root.val, root.val);
        return answer;
    }

    public void DFS(TreeNode node, int max, int min) {
        if(node == null) {
            return;
        }

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

        if (node.left == null && node.right == null) {
            answer = Math.max(answer, max - min);
        }

        DFS(node.left, max, min);
        DFS(node.right, max, min);
    }
}

• 핵심은 |a-b|가 가장 클려면, a와 b가 최대값, 최소값으로 구성되어야한다는 것
• 리프노드일 때, max - min 값을 구하면 해당 경로의 |a-b|의 최대값을 구할 수 있음
• 해당 조상 노드까지의 max / min을 구하고 왼쪽 경로를 타고 쭉 내려가고, 다시 백트래킹해서 조상 노드까지의 max / min 값을 가지고 오른쪽 경로를 타고 쭉 내려가는 식..