推 pandix: 大師 12/09 11:32
推 DDFox: 大師 12/09 11:37
推 sustainer123: 大師 12/09 11:42
1026. Maximum Difference Between Node and Ancestor
給予一個二元樹，找出最大的值v，v為兩個相異的節點a和b之值相減之絕對值，a必須
滿足他是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：
https://assets.leetcode.com/uploads/2020/11/09/tmp-tree.jpg
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.
思路：
1.可以用dfs遍歷所有節點，並記錄父節點的最大值和最小值，最大的絕對值差一定是
當前節點減去最大或最小。
Java Code：
------------------------------------
class Solution {
public int maxAncestorDiff(TreeNode root) {
return maxAncestorDiff(root, root.val, root.val);
}
private int maxAncestorDiff(TreeNode root, int max, int min) {
if (root == null) {
return 0;
}
int res = Math.max(Math.abs(root.val - max), Math.abs(root.val -
min));
max = Math.max(max, root.val);
min = Math.min(min, root.val);
res = Math.max(res, maxAncestorDiff(root.left, max, min));
res = Math.max(res, maxAncestorDiff(root.right, max, min));
return res;
}
}
------------------------------------
--
https://i.imgur.com/bFRiqA3.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.74.170 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1670556286.A.00C.html