.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
๋Œ“๊ธ€์“ฐ๊ธฐ ํผ