1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    private int ans;

    public int maxAncestorDiff(TreeNode root) {
        helper(root, root.val, root.val);
        return ans;
    }

    private void helper(TreeNode node, int currMax, int currMin) {
        if (node == null)
            return;
        ans = Math.max(ans, Math.max(Math.abs(node.val - currMax), Math.abs(node.val - currMin)));
        int newMax = Math.max(currMax, node.val), newMin = Math.min(currMin, node.val);
        helper(node.left, newMax, newMin);
        helper(node.right, newMax, newMin);
    }
}

就是到达某个node时, 我们需要告诉它, 它的ancestors的最大值和最小值是多少. 然后和最大值最小值做差取绝对值, 看哪个大, 大的那个就是该node能凑成的最大的值.

时间复杂度: O(n)
空间复杂度: O(n)