leetcode 1026, Maximum Difference Between Node and Ancestor

NJW·2022년 12월 9일

코테

목록 보기

122/170

들어가는 말

이진 트리에서 두 값을 뺀 절대값이 최대가 되도록 하는 문제다. 단, 여기서 두 값은 부모와 자식의 관계로 이루어져야 한다.

최대값과 최소값을 구해서 빼주면 된다고 생각지만, 단순히 전체 탐색만을 적용할 경우 최대값과 최소값이 부모 자식의 관계가 아닐 수 있다.
이 부분을 해결하지 못해서 결국 솔루션을 확인했다.

솔루션에서는 left와 rigth로 나눠서 각 방향 별로 구한 최대값과 최소값을 구해 빼주도록 했다. 그리고 left와 right를 서로 비교하는 식이다. 이렇게 하면 두 노드 간에 관계가 부모와 자식을 유지할 수 있다.

코드 설명

먼저 주어진 root가 null일 경우를 대비해 0을 리턴하도록 한다.
DFS를 실행한다.
2-1. 만일 해당 노드가 null(직전의 노드가 단말 노드)이라면 지금까지 구한 최대값과 최소값을 뺀 절대값을 구해서 리턴한다.
2-2. 해당 노드에 값이 있다면 max와 비교해 해당 노드의 값이 더 크면 max를 갱신해준다.
2-3. 해당 노드에 값이 있다면 min과 비교해 해당 노드의 값이 더 작으면 min을 갱신해준다.
2-4. 해당 노드의 왼쪽 노드를 탐색한다. 여기서 max와 min은 해당 노드의 왼쪽 노드의 부모 노드이기 때문에 계속 가져가도 된다.
2-5. 해당 노드의 오른쪽 노드를 탐색한다. 여기서 max와 min은 해당 노드의 오른쪽 노드의 부모 노드이기 때문에 계속 가져가도 된다.
2-6. 왼쪽 노드와 오른쪽 노드를 전부 탐색했다면, 더 큰 값을 리턴하도록 한다.

코드

/**
 * 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 {

    public int maxAncestorDiff(TreeNode root) {

        if(root == null){
            return 0;
        }

        return DFS(root, root.val, root.val);

    }

    public int DFS(TreeNode node, int max, int min){
        if(node == null){
            return Math.abs(max - min);
        }

        if(max < node.val){
            max = node.val;
        }
        if(min > node.val){
            min = node.val;
        }

        int left = DFS(node.left, max, min);
        int right = DFS(node.right, max, min);

        return Math.max(left, right);
    }
}