8000 solution to max-level-sum-bin-tree · AlgoBBA/awesome-golang-algorithm@ba8e6a8 · GitHub
[go: up one dir, main page]
Skip to content

Commit ba8e6a8

Browse files
vortex-17vortex-17
committed
solution to max-level-sum-bin-tree
1 parent afdc693 commit ba8e6a8

File tree

4 files changed

+118
-9
lines changed

4 files changed

+118
-9
lines changed

‎leetcode/1101-1200/1161.Maximum-Level-Sum-of-a-Binary-Tree/README.md

Lines changed: 11 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -4,14 +4,23 @@
44
> This question is temporarily unanswered if you have good ideas. Welcome to [Create Pull Request PR](https://github.com/kylesliu/awesome-golang-algorithm)
55
66
## Description
7+
Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.
78

9+
Return the smallest level X such that the sum of all the values of nodes at level X is maximal.
810
**Example 1:**
911

1012
```
11-
Input: a = "11", b = "1"
12-
Output: "100"
13+
Input: root = [1,7,0,7,-8,null,null]
14+
Output: 2
15+
Explanation:
16+
Level 1 sum = 1.
17+
Level 2 sum = 7 + 0 = 7.
18+
Level 3 sum = 7 + -8 = -1.
19+
So we return the level with the maximum sum which is level 2.
1320
```
1421

22+
Link to question: https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/
23+
1524
## 题意
1625
> ...
1726

‎leetcode/1101-1200/1161.Maximum-Level-Sum-of-a-Binary-Tree/Solution.go

Lines changed: 55 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,58 @@
11
package Solution
22

3-
func Solution(x bool) bool {
4-
return x
3+
/**
4+
* Definition for a binary tree node.
5+
* type TreeNode struct {
6+
* Val int
7+
* Left *TreeNode
8+
* Right *TreeNode
9+
* }
10+
*/
11+
type TreeNode struct {
12+
Val int
13+
Left *TreeNode
14+
Right *TreeNode
15+
}
16+
17+
func maxLevelSum(root *TreeNode) int {
18+
tree := make(map[*TreeNode]int)
19+
tree[root] = 0
20+
var treeList []*TreeNode
21+
treeList = append(treeList, root)
22+
sum := root.Val
23+
l := 0
24+
var sumList []int
25+
level := tree[root]
26+
for len(treeList) > 0 {
27+
r := treeList[0]
28+
treeList = treeList[1:]
29+
30+
if tree[r] > level {
31+
sumList = append(sumList, sum)
32+
sum = 0
33+
level = tree[r]
34+
}
35+
sum += r.Val
36+
37+
if r.Left != nil {
38+
treeList = append(treeList, r.Left)
39+
tree[r.Left] = level + 1
40+
}
41+
42+
if r.Right != nil {
43+
treeList = append(treeList, r.Right)
44+
tree[r.Right] = level + 1
45+
}
46+
47+
}
48+
49+
sumList = append(sumList, sum)
50+
max := sumList[0]
51+
for i, j := range sumList {
52+
if j > max {
53+
max = j
54+
l = i
55+
}
56+
}
57+
return l + 1
558
}

‎leetcode/1101-1200/1161.Maximum-Level-Sum-of-a-Binary-Tree/Solution_test.go

Lines changed: 52 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -6,16 +6,63 @@ import (
66
"testing"
77
)
88

9+
type TreeNode struct {
10+
Val int
11+
Left *TreeNode
12+
Right *TreeNode
13+
}
14+
15+
type BinaryTree struct {
16+
root *TreeNode
17+
}
18+
19+
func (t *BinaryTree) insert(data int) *BinaryTree {
20+
if t.root == nil {
21+
t.root = &TreeNode{Val: data, Left: nil, Right: nil}
22+
} else {
23+
t.root.insert(data)
24+
}
25+
return t
26+
}
27+
28+
func (n *TreeNode) insert(data int) {
29+
if n == nil {
30+
return
31+
} else if data <= n.Val {
32+
if n.Left == nil {
33+
n.Left = &TreeNode{Val: data, Left: nil, Right: nil}
34+
} else {
35+
n.Left.insert(data)
36+
}
37+
} else {
38+
if n.Right == nil {
39+
n.Right = &TreeNode{Val: data, Left: nil, Right: nil}
40+
} else {
41+
n.Right.insert(data)
42+
}
43+
}
44+
}
45+
46+
func main() {
47+
48+
}
49+
950
func TestSolution(t *testing.T) {
1051
// 测试用例
52+
// The original Problem requires the binary tree constructed from array. Please refer to test cases produced at Leetcode problem https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/
53+
tree1 := &BinaryTree{}
54+
tree1.insert(1).
55+
insert(7).
56+
insert(0).
57+
insert(7).
58+
insert(-8)
59+
1160
cases := []struct {
1261
name string
13-
inputs bool
14-
expect bool
62+
inputs *BinaryTree
63+
expect int
1564
}{
16-
{"TestCase", true, true},
17-
{"TestCase", true, true},
18-
{"TestCase", false, false},
65+
{"TestCase1", tree1, 2},
1966
}
2067

2168
// 开始测试

‎test.sh

100644100755
File mode changed.

0 commit comments

Comments
 (0)
0