.Zzumbong

[leetCode/JS] 124. Binary Tree Maximum Path Sum ๋ณธ๋ฌธ

coding test/leetCode

[leetCode/JS] 124. Binary Tree Maximum Path Sum

์ญ˜๋ด‰ 2022. 12. 11. 11:45

๋‚œ์ด๋„ [ ๐Ÿ‘ฟ ] Hard 

 

๋ฌธ์ œ ์„ค๋ช… 

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

์ด์ง„ ํŠธ๋ฆฌ์˜ ์—ฐ์†๋œ ๊ฒฝ๋กœ์ค‘์— ์ตœ๋Œ€ ํ•ฉ์‚ฐ์„ ๋ฐ˜ํ™˜ํ•˜๋ฉด ๋œ๋‹ค. ๋ฃจํŠธ๋ฅผ ํ†ต๊ณผํ•  ํ•„์š”๊ฐ€ ์—†๋‹ค.

 

 

์ž…์ถœ๋ ฅ ์˜ˆ

Example 1:

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

 

Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

 

 

Constraints

  • The number of nodes in the tree is in the range [1, 3 * 104].
  • -1000 <= Node.val <= 1000

 

 

 


 

๋‚ด ์†”๋ฃจ์…˜

  • DFS๋กœ ์„œ์น˜ํ•œ๋‹ค. ํ˜„์žฌ ๊ฒฝ๋กœ์˜ ํ•ฉ๊ณ„๋ฅผ ์ €์žฅํ•ด ๋‘”๋‹ค.
  • dfs()์˜ return์€ left, right ๋…ธ๋“œ์ค‘ ๊ฐ€์žฅ ํฐ ๊ฐ’์„ ๋ฆฌํ„ดํ•œ๋‹ค.

  • return์„ 0, node.val+left, node.val+right๋ฅผ ํ•˜๋Š” ์ด์œ ๋Š” ๊ฒฝ๋กœ์˜ ๋ฌธ์ œ๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.
  • 0์„ ๋น„๊ตํ•˜๋Š” ๊ฒƒ์€ ํ•ฉ๊ณ„๊ฐ€ ๋งˆ์ด๋„ˆ์Šค๊ฐ€ ๋‚˜์˜ค๊ธฐ๋„ํ•ด์„œ ํ•˜์œ„ ๋…ธ๋“œ ๊ฒฝ๋กœ๋ฅผ ๋ฒ„๋ฆด ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค.
var maxPathSum = function(root) {
  let max = -Infinity;
  const dfs = (node) => {
    if(!node) return 0;
    const left = dfs(node.left);
    const right = dfs(node.right);
    max = Math.max(max, node.val + left + right)
    return Math.max(0, node.val + left, node.val + right);
  }
  dfs(root);
  return max;
};

 

๊ฐ์ƒํ‰

  • ๋ช‡์ผ์ „ ํ’€์—ˆ๋˜ 1026๋ฒˆ ๋ฌธ์ œ์™€ ์ •๋ง ๋น„์Šทํ–ˆ๋‹ค.
  • 12์›”์€ DFS๋ฌธ์ œ๋งŒ ์Ÿ์•„์ง€๋Š” ์ค‘

'coding test > leetCode' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[leetCode/JS] 931. Minimum Falling Path Sum  (0) 2022.12.13
[leetCode/JS] 70. Climbing Stairs  (0) 2022.12.12
[leetCode/JS] 1339. Maximum Product of Splitted Binary Tree  (0) 2022.12.10
[leetCode/JS] 1026. Maximum Difference Between Node and Ancestor  (0) 2022.12.09
[leetCode/JS] 872. Leaf-Similar Trees  (0) 2022.12.08
Comments