Notice
Recent Posts
Recent Comments
Link
์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- ๊ฒ์
- ์ ์ค
- ํ์ค์คํค
- ์ ์ฅ
- ์ก๋ฆฌ๋จ
- Sort
- javascript
- ์ฝ๋ฉํ ์คํธ
- ๋ง์ง
- ์กํ
- ์ฝํ
- ์ฐ์ฃผ
- ๋์ซ
- LeetCode
- ์ ํฌ๋ธ
- ์ ์ค์๋ด
- ์๊ณ ๋ฆฌ์ฆ
Archives
- Today
- Total
.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 |
Comments