문제링크: https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/description/

---

1. 문제설명

트리의 조상과 자식 노드사이에서 발생할 수 있는 가장 큰 차를 찾는 문제.

1.1. 입출력 예시

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.

Example 2:

Input: root = [1,null,2,null,0,3]
Output: 3

1.2. 제한사항

• 트리에 들어갈 수 있는 노드의 개수는 [2, 5000]
• 0 <= Node.val <= 10^5

---

2. 풀이

2.1. 나의 생각

트리 전체를 순회하여 최소값과 최댓값을 구해서 그 차를 구하는 문제가 아니다. 각 노드에 도달 했을 때 사용할 수 있는 정보는 그 자식노드에서 탐색한 최대 최소값이기 때문이다. 따라서 이 문제는 깊이우선탐색(Depth-First-Search)를 활용하여 각 노드에서 현제 사용할 수 있는 정보를 자식노드로 부터 받아온 후 그 시점에서 도출 할 수 있는 최선의 답을 전역변수에 저장하는 방식으로 문제를 해결하였다.

코드:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private static int maxDifferent=0;
    static class ExtremumValue{
        int min, max;
        ExtremumValue(int min, int max){
            this.min = min;
            this.max = max;
        }
        public void setExtremum(int min, int max){
            if(this.min>min) this.min = min;
            if(this.max<max) this.max = max;
        }
    }
    public static int maxAncestorDiff(TreeNode root) {
        searchExtremum(root);
        int ans = maxDifferent;
        maxDifferent = 0;
        return ans;
    }
    public static ExtremumValue searchExtremum(TreeNode node){
        ExtremumValue current = new ExtremumValue(node.val, node.val);
        ExtremumValue descendent;
        if(node.left!=null){
            descendent = searchExtremum(node.left);
            current.setExtremum(descendent.min, descendent.max);
        }
        if(node.right!=null){
            descendent = searchExtremum(node.right);
            current.setExtremum(descendent.min, descendent.max);
        }

        int currentMax = Math.max(Math.abs(current.min-node.val), Math.abs(current.max-node.val));
        maxDifferent = Math.max(maxDifferent, currentMax);

        return current;
    }
}

2.2. 결과