[leetcode #1026] Maximum Difference Between Node and Ancestor

Problem

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.

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

Constraints:

・ The number of nodes in the tree is in the range [2, 5000].
・ 0 <= Node.val <= 105

Idea

Recursive function을 이용해 Tree를 탐색하는 것에 익숙한 사람이라면 쉽게 풀 수 있는 문제다.

조상 노드 값과 자식 노드 사이 값의 차가 최대가 되는 경우를 구하는 문제다.

우선 root node의 값을 최소값과 최대값으로 설정하고 재귀함수를 호출한다.

재귀함수에서는 node가 null일 때 최대값에서 최소값을 뺀 값을 리턴한다.
현재 node가 null이 아닌 경우는 현재 노드의 값과 최소・최대값을 비교해 최소값과 최대값을 다시 설정해준다.
왼쪽 자식 노드와 오른쪽 자식 노드를 인자로 하여 다시 재귀함수를 호출한다. 왼쪽 자식 노드와 오른쪽 자식 노드를 인자로 하여 받은 값 중 더 큰 값을 리턴해준다.

Solution

/**
 * 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) {
        return traverseTree(root, root.val, root.val);
    }

    private int traverseTree(TreeNode node, Integer min, Integer max) {
        if (node == null) {
            return max - min;
        }

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

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

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

Reference

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