LeetCode 솔루션 분류
[interview] 1026. Maximum Difference Between Node and Ancestor
본문
Medium
239464Add to ListShareGiven 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
관련자료
-
링크
댓글 3
mingki님의 댓글
- 익명
- 작성일
C++
Runtime: 14 ms, faster than 19.81% of C++ online submissions for Maximum Difference Between Node and Ancestor.
Memory Usage: 9.8 MB, less than 58.79% of C++ online submissions for Maximum Difference Between Node and Ancestor.
Runtime: 14 ms, faster than 19.81% of C++ online submissions for Maximum Difference Between Node and Ancestor.
Memory Usage: 9.8 MB, less than 58.79% of C++ online submissions for Maximum Difference Between Node and Ancestor.
class Solution {
public:
int maxAncestorDiff(TreeNode* root, int minVal = 1e5 + 1, int maxVal = -1e5 - 1) {
if (!root) return 0;
int tmp = minVal > 1e5 ? 0 :
max(abs(minVal - root->val), abs(maxVal - root->val));
minVal = min(minVal, root->val);
maxVal = max(maxVal, root->val);
int child = max(maxAncestorDiff(root->left, minVal, maxVal), maxAncestorDiff(root->right, minVal, maxVal));
return max(tmp, child);
}
};
학부유학생님의 댓글
- 익명
- 작성일
Runtime: 73 ms, faster than 23.29% of Python3 online submissions for Maximum Difference Between Node and Ancestor.
Memory Usage: 20.3 MB, less than 19.92% of Python3 online submissions for Maximum Difference Between Node and Ancestor.
Memory Usage: 20.3 MB, less than 19.92% of Python3 online submissions for Maximum Difference Between Node and Ancestor.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
def dfs(node, minval, maxval):
if not node: return 0
temp = max(abs(node.val - minval), abs(node.val-maxval)) if minval < 10e5 else 0
minval = min(minval, node.val)
maxval = max(maxval, node.val)
temp2 = max(dfs(node.left, minval, maxval),dfs(node.right,minval,maxval))
return max(temp, temp2)
return dfs(root, 10e5, -10e5)
Coffee님의 댓글
- 익명
- 작성일
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int result = 0;
private void dfs(TreeNode node, int currMax, int currMin){
if(node == null){
return;
}
int currMaxDiff = Math.max(Math.abs(currMax - node.val), Math.abs(currMin - node.val));
result = Math.max(result, currMaxDiff);
currMax = Math.max(currMax, node.val);
currMin = Math.min(currMin, node.val);
dfs(node.left, currMax, currMin);
dfs(node.right, currMax, currMin);
return;
}
public int maxAncestorDiff(TreeNode root) {
if(root == null){
return 0;
}
dfs(root, root.val, root.val);
return result;
}
}