8000 feat: 2021年05月13日22:40:25 · chenshiwei-io/leetcode@40795b3 · GitHub
[go: up one dir, main page]
Skip to content

Commit 40795b3

Browse files
author
chen-shiwei
committed
feat: 2021年05月13日22:40:25
2 parents c911d04 + 6eca8e0 commit 40795b3

File tree

39 files changed

+1634
-84
lines changed

39 files changed

+1634
-84
lines changed

‎Makefile

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
.PHONY: update-readme
2+
update-readme:
3+
ls -1 leetcode | grep 树 > docs/tree.md

‎docs/tree.md

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
100.相同的树
2+
105.从前序与中序遍历序列构造二叉树
3+
106.从中序与后序遍历序列构造二叉树
4+
107.二叉树的层序遍历II
5+
111.二叉树的最小深度
6+
208.实现Trie(前缀树)
7+
222.完全二叉树的节点个数
8+
257.二叉树的所有路径
9+
429.N叉树的层序遍历
10+
501.二叉搜索树中的众数
11+
513.找树左下角的值
12+
530.二叉搜索树的最小绝对差
13+
572.另一个树的子树
14+
589.N叉树的前序遍历
15+
637.二叉树的层平均值
16+
654.最大二叉树
17+
700.二叉搜索树中的搜索
18+
783.二叉搜索树节点最小距离

‎leetcode/0098/is-valid-bst.go

Lines changed: 21 additions & 47 deletions
Original file line numberDiff line numberDiff line change
@@ -19,61 +19,35 @@ type TreeNode struct {
1919
}
2020

2121
func IsValidBST(root *TreeNode) bool {
22-
flag = math.MinInt32 - 1
23-
check = true
24-
2522
if root == nil {
2623
return true
2724
}
28-
checkBast(root)
2925

30-
return check
31-
}
26+
var (
27+
isBST = true
28+
checkBST func(node *TreeNode)
29+
flag = math.MinInt32 - 1
30+
)
31+
checkBST = func(node *TreeNode) {
32+
if node == nil {
33+
return
34+
}
3235

33-
var (
34-
flag int = math.MinInt32 - 1
35-
check bool = true
36-
)
36+
checkBST(node.Left)
37+
38+
if flag >= node.Val {
39+
isBST = false
40+
return
41+
}
42+
flag = node.Val
43+
44+
checkBST(node.Right)
3745

38-
func checkBast(node *TreeNode) {
39-
if node == nil {
40-
return
41-
}
42-
if node.Left != nil {
43-
checkBast(node.Left)
44-
}
45-
if flag >= node.Val {
46-
check = false
4746
return
48-
}
49-
flag = node.Val
50-
if node.Right != nil {
51-
checkBast(node.Right)
5247

5348
}
54-
return
55-
}
5649

57-
//func checkBst(node, lower, upper *TreeNode) bool {
58-
// if node == nil {
59-
// return true
60-
// }
61-
//
62-
// if lower != nil {
63-
// if node.Val <= lower.Val {
64-
// return false
65-
// }
66-
// }
67-
//
68-
// if upper != nil {
69-
// if node.Val >= upper.Val {
70-
// return false
71-
// }
72-
// }
73-
//
74-
// return checkBst(node.Left, lower, node) && checkBst(node.Right, node, upper)
75-
//}
50+
checkBST(root)
7651

77-
// 10
78-
//5 15
79-
// 6 20
52+
return isBST
53+
}

‎leetcode/100.相同的树/isSameTree.go

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package _00_相同的树
2+
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 isSameTree(p *TreeNode, q *TreeNode) bool {
18+
if p == nil && q == nil {
19+
return true
20+
}
21+
22+
if p == nil || q == nil {
23+
return false
24+
}
25+
26+
if p.Val != q.Val {
27+
return false
28+
}
29+
30+
// 如果 p.val == q.val 继续比对
31+
return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
32+
}

‎leetcode/100.相同的树/isSameTree_test.go

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
package _00_相同的树
2+
3+
import "testing"
4+
5+
func Test_isSameTree(t *testing.T) {
6+
type args struct {
7+
p *TreeNode
8+
q *TreeNode
9+
}
10+
tests := []struct {
11+
name string
12+
args args
13+
want bool
14+
}{
15+
{name: `输入：p = [1,2,3], q = [1,2,3]
16+
输出：true`, args: args{
17+
p: &TreeNode{
18+
Val: 1,
19+
Left: &TreeNode{
20+
Val: 2,
21+
Left: nil,
22+
Right: nil,
23+
},
24+
Right: &TreeNode{
25+
Val: 3,
26+
Left: nil,
27+
Right: nil,
28+
},
29+
},
30+
q: &TreeNode{
31+
Val: 1,
32+
Left: &TreeNode{
33+
Val: 2,
34+
Left: nil,
35+
Right: nil,
36+
},
37+
Right: &TreeNode{
38+
Val: 3,
39+
Left: nil,
40+
Right: nil,
41+
},
42+
},
43+
}, want: true},
44+
{name: `[1,2]
45+
[1,null,2]`, args: args{
46+
p: &TreeNode{
47+
Val: 1,
48+
Left: &TreeNode{
49+
Val: 2,
50+
Left: nil,
51+
Right: nil,
52+
},
53+
},
54+
q: &TreeNode{
55+
Val: 1,
56+
Left: nil,
57+
Right: &TreeNode{
58+
Val: 2,
59+
Left: nil,
60+
Right: nil,
61+
},
62+
},
63+
}},
64+
}
65+
for _, tt := range tests {
66+
t.Run(tt.name, func(t *testing.T) {
67+
if got := isSameTree(tt.args.p, tt.args.q); got != tt.want {
68+
t.Errorf("isSameTree() = %v, want %v", got, tt.want)
69+
}
70+
})
71+
}
72+
}

‎leetcode/0105/build_tree.go renamed to ‎leetcode/105.从前序与中序遍历序列构造二叉树/build_tree.go

Lines changed: 13 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package _105
1+
package _05_从前序与中序遍历序列构造二叉树
22

33
/**
44
* Definition for a binary tree node.
@@ -23,25 +23,33 @@ func buildTree(preorder []int, inorder []int) *TreeNode {
2323
return nil
2424
}
2525

26+
rootVal := preorder[0]
2627
rootNode := &TreeNode{
27-
Val: preorder[0],
28+
Val: rootVal,
2829
Left: nil,
2930
Right: nil,
3031
}
32+
preorder = preorder[1:]
3133

3234
// 找到根节点在中序遍历的位置
3335
// 根据中序遍历的特性 root节点左边的都是root节点的左子树，数量为(rootIndex+1)
3436
var rootIndex int
3537

3638
for i, v := range inorder {
37-
if v == preorder[0] {
39+
if v == rootVal {
3840
rootIndex = i
3941
break
4042
}
4143
}
4244

45+
leftInorder := inorder[:rootIndex]
46+
rightInorder := inorder[rootIndex+1:]
47+
48+
leftPreorder := preorder[:len(leftInorder)]
49+
rightPreorder := preorder[len(leftInorder):]
50+
4351
// 前序遍历的根节点的后面是左子树，左子树的切片为(1:rootIndex+1)
44-
rootNode.Left = buildTree(preorder[1:rootIndex+1], inorder[:rootIndex])
45-
rootNode.Right = buildTree(preorder[rootIndex+1:], inorder[rootIndex+1:])
52+
rootNode.Left = buildTree(leftPreorder, leftInorder)
53+
rootNode.Right = buildTree(rightPreorder, rightInorder)
4654
return rootNode
4755
}

‎leetcode/0105/build_tree_test.go renamed to ‎leetcode/105.从前序与中序遍历序列构造二叉树/build_tree_test.go

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package _105
1+
package _05_从前序与中序遍历序列构造二叉树
22

33
import (
44
"reflect"
@@ -45,7 +45,7 @@ func Test_buildTree(t *testing.T) {
4545
}
4646
for _, tt := range tests {
4747
t.Run(tt.name, func(t *testing.T) {
48-
if got := buildTree(tt.args.preorder, tt.args.inorder); !reflect.DeepEqual(got, tt.want) {
48+
if got := buildTree1(tt.args.preorder, tt.args.inorder); !reflect.DeepEqual(got, tt.want) {
4949
t.Errorf("buildTree() = %v, want %v", got, tt.want)
5050
}
5151
})

‎leetcode/106.从中序与后序遍历序列构造二叉树/buildTree.go

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package _06_从中序与后序遍历序列构造二叉树
2+
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 buildTree(inorder []int, postorder []int) *TreeNode {
18+
if len(postorder) == 0 {
19+
return nil
20+
}
21+
// 从后序遍历获取root
22+
rootVal := postorder[len(postorder)-1]
23+
root := &TreeNode{
24+
Val: rootVal,
25+
}
26+
if len(postorder) == 1 {
27+
return root
28+
}
29+
// 从后序遍历删除root
30+
postorder = postorder[:len(postorder)-1]
31+
32+
// 获取root在中序遍历的位置
33+
var rootIdx int
34+
for i := 0; i < len(inorder); i++ {
35+
if inorder[i] == rootVal {
36+
rootIdx = i
37+
break
38+
}
39+
}
40+
41+
// root在中序遍历的位置切分左右子树，后续根据前序切分的数组长度切分后续数组
42+
root.Left = buildTree(inorder[:rootIdx], postorder[:len(inorder[:rootIdx])])
43+
root.Right = buildTree(inorder[rootIdx+1:], postorder[len(inorder[:rootIdx]):])
44+
return root
45+
}

‎leetcode/106.从中序与后序遍历序列构造二叉树/buildTree_test.go

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package _06_从中序与后序遍历序列构造二叉树
2+
3+
import (
4+
"log"
5+
"reflect"
6+
"testing"
7+
)
8+
9+
func Test_buildTree(t *testing.T) {
10+
type args struct {
11+
inorder []int
12+
postorder []int
13+
}
14+
tests := []struct {
15+
name string
16+
args args
17+
want *TreeNode
18+
}{
19+
{name: `中序遍历 inorder = [9,3,15,20,7]
20+
后序遍历 postorder = [9,15,7,20,3]`, args: struct {
21+
inorder []int
22+
postorder []int
23+
}{inorder: []int{9, 3, 15, 20, 7}, postorder: []int{9, 15, 7, 20, 3}}},
24+
}
25+
for _, tt := range tests {
26+
t.Run(tt.name, func(t *testing.T) {
27+
got := buildTree(tt.args.inorder, tt.args.postorder)
28+
if !reflect.DeepEqual(got, tt.want) {
29+
t.Errorf("buildTree() = %v, want %v", got, tt.want)
30+
}
31+
32+
InEach(got)
33+
})
34+
}
35+
}
36+
37+
func InEach(root *TreeNode) {
38+
if root == nil {
39+
return
40+
}
41+
InEach(root.Left)
42+
log.Println(root.Val)
43+
InEach(root.Right)
44+
45+
return
46+
}

0 commit comments

Comments
 (0)
0