HackMD
1026.Maximum Difference Between Node and Ancestor
tags: Medium,Tree,Binary Tree,DFS
1026. Maximum Difference Between Node and Ancestor
題目描述
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<= 105
解答
Python
class Solution:
def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
self.currMaxDiff = 0
def getMaxDiff(node, currMax, currMin):
if not node:
return
currMax = max(currMax, node.val)
currMin = min(currMin, node.val)
self.currMaxDiff = max(self.currMaxDiff, abs(node.val - currMax), abs(node.val - currMin))
getMaxDiff(node.left, currMax, currMin)
getMaxDiff(node.right, currMax, currMin)
getMaxDiff(root, root.val, root.val)
return self.currMaxDiff
Kobe Dec 9, 2022
class Solution:
def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
def current_subtree_min(root):
Q = [root.val]
child_maxdiff = []
if root.left != None:
left_diff, left_limit = current_subtree_min(root.left)
Q += left_limit
child_maxdiff.append(left_diff)
if root.right != None:
right_diff, right_limit = current_subtree_min(root.right)
Q += right_limit
child_maxdiff.append(right_diff)
#print(root.val, max( [ abs(root.val - x) for x in Q] ), [min(Q), max(Q)])
#print( [abs(root.val - x) for x in Q])
return max( child_maxdiff+[ abs(root.val - x) for x in Q] ), [min(Q), max(Q)]
ans , _ = current_subtree_min(root)
return ans
玉山 Dec 10, 2022
C++
class Solution {
public:
int maxAncestorDiff(TreeNode* root, int alpha = INT_MAX, int beta = INT_MIN) {
if (!root) return 0;
alpha = min(alpha, root->val);
beta = max(beta, root->val);
return root->left == root->right ? beta - alpha : max(maxAncestorDiff(root->left, alpha, beta), maxAncestorDiff(root->right, alpha, beta));
}
};
Yen-Chi ChenFri, Dec 9, 2022
C#
public class Solution {
public int MaxAncestorDiff(TreeNode root) {
return MaxAncestorDiff(root, root.val, root.val);
}
private int MaxAncestorDiff(TreeNode node, int min, int max){
if (node == null) return 0;
min = Math.Min(node.val, min);
max = Math.Max(node.val, max);
int diff = max - min;
diff = Math.Max(diff, MaxAncestorDiff(node.left, min, max));
diff = Math.Max(diff, MaxAncestorDiff(node.right, min, max));
return diff;
}
}
JimFri, Dec 9, 2022
Javascript
function maxAncestorDiff(root) {
if (root === null) return 0;
return dfs(root, root.val, root.val);
}
function dfs(node, min, max) {
if (node === null) return max - min;
min = Math.min(min, node.val);
max = Math.max(max, node.val);
return Math.max(dfs(node.left, min, max), dfs(node.right, min, max));
}
MarsgoatTue, Feb 21, 2023
