LeetCode1026-节点与其祖先之间的最大差值

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/maximum-difference-between-node-and-ancestor/

中文链接：https://leetcode-cn.com/problems/maximum-difference-between-node-and-ancestor/

题目详述

给定二叉树的根节点 root，找出存在于不同节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。

（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）

示例：

img

1
2
3
4
5
6
7
8
9
输入：[8,3,10,1,6,null,14,null,null,4,7,13]
输出：7
解释： 
我们有大量的节点与其祖先的差值，其中一些如下：
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。

提示：

  1. 树中的节点数在 2 到 5000 之间。
  2. 每个节点的值介于 0 到 100000 之间。

题目详解

方法一：自底向上的计算方法。

  • 如果对于每一个节点，我们知道它的左子树中结点最小值和最大值、它的右子树中结点最小值和最大值，那么由当前结点作为祖先结点的最大值可以很容易求出。
  • 可以实现一个求子树最小值和最大值的方法，在递归过程中不断更新结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class LeetCode_01026 {

    // 自底向上计算
    public int maxAncestorDiff(TreeNode root) {
        int[] res = new int[]{Integer.MIN_VALUE};
        dfs(root, res);
        return res[0];
    }

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

方法一：自顶向下的计算方法。

  • 可以换一种思路，把当前路径上的最小值和最大值往下传递，并进行更新。
  • 到达当前结点时，已经知道从根结点到当前结点的最小值和最大值，这样可以直接更新结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class LeetCode_01026 {

    // 自顶向下计算
    public int maxAncestorDiff(TreeNode root) {
        return dfs(root, root.val, root.val);
    }

    private int dfs(TreeNode root, int min, int max) {
        min = Math.min(min, root.val);
        max = Math.max(max, root.val);
        if (root.left == null && root.right == null) return max - min;
        if (root.left == null) return dfs(root.right, min, max);
        if (root.right == null) return dfs(root.left, min, max);
        return Math.max(dfs(root.left, min, max), dfs(root.right, min, max));
    }
}

自顶向下的计算方法的另一种更简洁写法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class LeetCode_01026 {

    // 自顶向下计算
    public int maxAncestorDiff(TreeNode root) {
        int[] res = new int[]{Integer.MIN_VALUE};
        dfs(root, root.val, root.val, res);
        return res[0];
    }

    private void dfs(TreeNode root, int min, int max, int[] res) {
        if (root == null) {
            return;
        }
        min = Math.min(min, root.val);
        max = Math.max(max, root.val);
        res[0] = Math.max(res[0], max - min);
        dfs(root.left, min, max, res);
        dfs(root.right, min, max, res);
    }
}