题目

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:

image.png

  1. Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
  2. Output: 7
  3. Explanation: We have various ancestor-node differences, some of which are given below :
  4. |8 - 3| = 5
  5. |3 - 7| = 4
  6. |8 - 1| = 7
  7. |10 - 13| = 3
  8. Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.

Example 2:

image.png

  1. Input: root = [1,null,2,null,0,3]
  2. Output: 3

Constraints:

  • The number of nodes in the tree is in the range [2, 5000].
  • 0 <= Node.val <= 10^5

题意

找到一组结点，其中一个是另一个祖先结点，使得这两个结点的差值最大。

思路

递归处理，两种方法：

  1. 每次找到左子树和右子树中的最值，以此更新结果。
  2. 每次递归更新当前路径上的最大值和最小值，到达叶结点时计算差值并返回。

代码实现

Java

递归1

  1. class Solution {
  2.     private int diff;
  4.     public int maxAncestorDiff(TreeNode root) {
  5.         diff = 0;
  6.         dfs(root);
  7.         return diff;
  8.     }
  10.     private int[] dfs(TreeNode root) {
  11.         if (root == null) {
  12.             return null;
  13.         }
  15.         int[] l = dfs(root.left), r = dfs(root.right);
  17.         if (l == null && r == null) {
  18.             return new int[] { root.val, root.val };
  19.         }
  21.         int cMin = 0, cMax = 0;
  22.         if (l != null && r != null) {
  23.             cMin = Math.min(l[0], r[0]);
  24.             cMax = Math.max(l[1], r[1]);
  25.         } else if (l != null) {
  26.             cMin = l[0];
  27.             cMax = l[1];
  28.         } else {
  29.             cMin = r[0];
  30.             cMax = r[1];
  31.         }
  32.         diff = Math.max(diff, Math.max(Math.abs(root.val - cMin), Math.abs(root.val - cMax)));
  33.         return new int[] { Math.min(root.val, cMin), Math.max(root.val, cMax) };
  34.     }
  35. }

递归2

  1. class Solution {
  2.     public int maxAncestorDiff(TreeNode root) {
  3.         if (root == null) {
  4.             return 0;
  5.         }
  7.         return dfs(root, root.val, root.val);
  8.     }
  10.     private int dfs(TreeNode root, int max, int min) {
  11.         if (root == null) {
  12.             return max - min;
  13.         }
  15.         max = Math.max(root.val, max);
  16.         min = Math.min(root.val, min);
  17.         return Math.max(dfs(root.left, max, min), dfs(root.right, max, min));
  18.     }
  19. }