Notice
Recent Posts
Recent Comments
Link
.Zzumbong
[leetCode/JS] 124. Binary Tree Maximum Path Sum ๋ณธ๋ฌธ
๋์ด๋ [ ๐ฟ ] 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 |
0 Comments