forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathobzva.go
More file actions
61 lines (58 loc) ยท 1.64 KB
/
obzva.go
File metadata and controls
61 lines (58 loc) ยท 1.64 KB
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/*
ํ์ด
- post order traversal dfs๋ฅผ ํ์ฉํ์ฌ ํ์ดํ ์ ์์ต๋๋ค
Big O
- N: node์ ๊ฐ์
- H: Tree์ ๋์ด
- Time compleixty: O(N)
- ๋ชจ๋ node๋ฅผ ์ต๋ ํ ๋ฒ ํ์ํฉ๋๋ค
- Space complexity: O(H)
- ์ฌ๊ท ํธ์ถ ์คํ์ ๊น์ด๋ H์ ๋น๋กํ์ฌ ์ฆ๊ฐํฉ๋๋ค
*/
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxPathSum(root *TreeNode) int {
res := root.Val
var maxSubtreeSum func(*TreeNode) int
maxSubtreeSum = func(node *TreeNode) int {
// base case
if node == nil {
return 0
}
// left subtree๋ก ๋ด๋ ค๊ฐ์ ๋ ๊ตฌํ ์ ์๋ maximum path sum
// left subtree๋ก path๋ฅผ ๋ด๋ ค๊ฐ์ ๋, left subtree๊ฐ sum์ ๊ธฐ์ฌํ๋ ๊ฐ์ด 0๋ณด๋ค ์์ ๊ฒฝ์ฐ
// left subtree๋ก๋ path๋ฅผ ๋ด๋ ค๊ฐ์ง ์๋ ๊ฒ์ด ์ข์
// ๋ฐ๋ผ์ left < 0 ์ธ ๊ฒฝ์ฐ์ left = 0
left := maxSubtreeSum(node.Left)
if left < 0 {
left = 0
}
// right subtree๋ left subtree์ ๋์ผํจ
right := maxSubtreeSum(node.Right)
if right < 0 {
right = 0
}
// ํ์ฌ ํ์ํ๊ณ ์๋ node์ ์กฐ์ node๋ฅผ path์ ํฌํจํ์ง ์๊ณ ๋
// maxPathSum์ด ๊ตฌํด์ง๋ ๊ฒฝ์ฐ๊ฐ ์์
if res < left+right+node.Val {
res = left + right + node.Val
}
// ํ์ฌ๊น์ง ๊ณ์ฐํ subtree path sum์ ๋ถ๋ชจ node์๊ฒ ์ ๋ฌํด์ผ ํจ
// ํ์ฌ node์ ๋ถ๋ชจ์ ์ด์ด์ง๋ path์ฌ์ผ ํ๋ฏ๋ก, node.Val + max(left, right)๋ฅผ ๋ฐํํ๋ฉด ๋จ
subTreeSum := node.Val
if left > right {
subTreeSum += left
} else {
subTreeSum += right
}
return subTreeSum
}
maxSubtreeSum(root)
return res
}