[릿코드] 1026. Maximum Difference Between Node and Ancestor

 

 

부모 노드와 자식 노드 값 차이의 절대값중 가장 큰 값을 구하는 문제로 Map<Integer, List<Integer>> 를 만들어서 노드마다 자식 노드 값을 저장했더니 효율성이 처참하게 나왔다. 

 

public void DFS(TreeNode node, int max, int min) {
    if (node == null) {
        return;
    }
    int newMax = Math.max(max, node.val);
    int newMin = Math.min(min, node.val);

    answer = Math.max(answer, Math.abs(newMax - newMin));

    DFS(node.left, newMax, newMin);
    DFS(node.right, newMax, newMin);
}

 

최대값, 최소값을 갱신하면서 재귀로 호출하면 현재 노드부터 최상위 노드중 최대값, 최소값의 차이를 구하기 때문에 노드마다 일일이 계산할 필요가 없다.

 

 

Maximum Difference Between Node and Ancestor - LeetCode