Notice
Recent Posts
Recent Comments
Link
.Zzumbong
[leetCode/JS] 1026. Maximum Difference Between Node and Ancestor ๋ณธ๋ฌธ
coding test/leetCode
[leetCode/JS] 1026. Maximum Difference Between Node and Ancestor
์ญ๋ด 2022. 12. 9. 10:48๋์ด๋ [ ๐ค ] Medium
๋ฌธ์ ์ค๋ช
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
.
์ด์งํธ๋ฆฌ์ ์์, ํ์ ๋ ธ๋์ a-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
๋ด ์๋ฃจ์
- 2์งํธ๋ฆฌ DFS๋ก ์์นํ๋ค.
- left, right๋ก ๋๋ ์ง ํธ๋ฆฌ๋ฅผ ์์นํ๋ฉด์ max, min์ ๊ตฌํ๋ค.
- ๋ง์ง๋ง ๋ ธ๋์ผ๋ max - min ํด์ left์ right ํธ๋ฆฌ์ ํฐ ๊ฐ์ ๋ฆฌํดํ๋ค.
var maxAncestorDiff = function(root) {
const dfs = (node, max, min) => {
if(!node) return Math.abs(max - min);
max = Math.max(max, node.val)
min = Math.min(min, node.val)
let leftMax = dfs(node.left, max, min);
let rightMax = dfs(node.right, max, min);
return Math.max(leftMax, rightMax)
}
return dfs(root, 0, Infinity);
};
๊ฐ์ํ
- return ๊ฐ์ ์ด์ฉํ์ฌ dfs๋ก ํ๋ฉด ์ฝ๋ค.
- ์์ฆ ์ด์งํธ๋ฆฌ ์์น๋ dfs ์์ฃผ๋ก ๋์์ ๋๋ถ์ DFS์ ์์ ๊ฐ์ด ๋ง์ด ์๊ฒผ๋ค.
'coding test > leetCode' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[leetCode/JS] 124. Binary Tree Maximum Path Sum (0) | 2022.12.11 |
---|---|
[leetCode/JS] 1339. Maximum Product of Splitted Binary Tree (0) | 2022.12.10 |
[leetCode/JS] 872. Leaf-Similar Trees (0) | 2022.12.08 |
[leetCode/JS] 938. Range Sum of BST (0) | 2022.12.07 |
[leetCode/JS] 328. Odd Even Linked List (0) | 2022.12.06 |
0 Comments