Maximum Difference Between Node and Ancestor (M)
題目
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 <= 10^5
題意
找到一組結點，其中一個是另一個祖先結點，使得這兩個結點的差值最大，
思路
遞回處理，兩種方法：
- 每次找到左子樹和右子樹中的最值，以此更新結果，
- 每次遞回更新當前路徑上的最大值和最小值，到達葉結點時計算差值并回傳，
代碼實作
Java
遞回1
class Solution {
private int diff;
public int maxAncestorDiff(TreeNode root) {
diff = 0;
dfs(root);
return diff;
}
private int[] dfs(TreeNode root) {
if (root == null) {
return null;
}
int[] l = dfs(root.left), r = dfs(root.right);
if (l == null && r == null) {
return new int[] { root.val, root.val };
}
int cMin = 0, cMax = 0;
if (l != null && r != null) {
cMin = Math.min(l[0], r[0]);
cMax = Math.max(l[1], r[1]);
} else if (l != null) {
cMin = l[0];
cMax = l[1];
} else {
cMin = r[0];
cMax = r[1];
}
diff = Math.max(diff, Math.max(Math.abs(root.val - cMin), Math.abs(root.val - cMax)));
return new int[] { Math.min(root.val, cMin), Math.max(root.val, cMax) };
}
}
遞回2
class Solution {
public int maxAncestorDiff(TreeNode root) {
if (root == null) {
return 0;
}
return dfs(root, root.val, root.val);
}
private int dfs(TreeNode root, int max, int min) {
if (root == null) {
return max - min;
}
max = Math.max(root.val, max);
min = Math.min(root.val, min);
return Math.max(dfs(root.left, max, min), dfs(root.right, max, min));
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/209270.html
標籤：其他