Leetcode 1026. Maximum Difference Between Node and Ancestor

[Woodyiiiiiii]

1026. Maximum Difference Between Node and Ancestor

这里有两种解法。

一、自底向上——归

这种写法也是大多数dfs、记忆化搜索的写法。将每个结点看成祖先，求它左右子结点的最小值和最大值，所以返回值是多个，要返回数组。后序遍历的翻版。

class Solution {

    int ans = 0;

    public int maxAncestorDiff(TreeNode root) {
        dfs(root);
        return ans;    
    }

    private int[] dfs(TreeNode root) {
        if (root == null) {
            return new int[]{-1,-1};
        }
        int[] left = dfs(root.left);
        int[] right = dfs(root.right);
        int max = root.val, min = root.val;
        if (left[0] != -1) {
            ans = Math.max(ans, Math.abs(left[0] - root.val));
            ans = Math.max(ans, Math.abs(left[1] - root.val));
            min = Math.min(min, left[0]);
            max = Math.max(max, left[1]);
        }
        if (right[0] != -1) {
            ans = Math.max(ans, Math.abs(right[0] - root.val));
            ans = Math.max(ans, Math.abs(right[1] - root.val));
            min = Math.min(min, right[0]);
            max = Math.max(max, right[1]);
        }
        return new int[]{min, max};
    }
}

二、自顶向下——递

这种写法是跟上述反过来。将每个结点看成子结点，求所有祖先结点的最小值和最大值。先序遍历的翻版。

class Solution {

    int ans = 0;

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

    private void dfs(TreeNode root, int mn, int mx) {
        if (root == null) return;
        mn = Math.min(root.val, mn);
        mx = Math.max(root.val, mx);
        ans = Math.max(ans, Math.max(Math.abs(root.val - mn), Math.abs(root.val - mx)));
        dfs(root.left, mn, mx);
        dfs(root.right, mn, mx);
    }
}

---

• 1026. Maximum Difference Between Node and Ancestor
• 98. Validate Binary Search Tree
• 104. Maximum Depth of Binary Tree
• 1372. Longest ZigZag Path in a Binary Tree
• 1110. Delete Nodes And Return Forest