8000 feat: 2021年05月11日21:06:16 · chenshiwei-io/leetcode@3496407 · GitHub
[go: up one dir, main page]
Skip to content

Commit 3496407

Browse files
author
陈世伟
committed
feat: 2021年05月11日21:06:16
1 parent 02dd95d commit 3496407

File tree

13 files changed

+621
-13
lines changed

13 files changed

+621
-13
lines changed

‎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/111.二叉树的最小深度/minDepth.go

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
package _11_二叉树的最小深度
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+
12+
type TreeNode struct {
13+
Val int
14+
Left *TreeNode
15+
Right *TreeNode
16+
}
17+
18+
func minDepth(root *TreeNode) int {
19+
return getDepth(root)
20+
}
21+
22+
func getDepth(root *TreeNode) int {
23+
if root == nil {
24+
return 0
25+
}
26+
27+
left := getDepth(root.Left)
28+
right := getDepth(root.Right)
29+
30+
if root.Left == nil && root.Right != nil {
31+
return right + 1
32+
}
33+
if root.Left != nil && root.Right == nil {
34+
return left + 1
35+
}
36+
37+
if root.Right == nil && root.Left == nil {
38+
return 1
39+
}
40+
41+
return min(left, right) + 1
42+
43+
}
44+
45+
func min(a, b int) int {
46+
if a > b {
47+
return b
48+
}
49+
return a
50+
}

‎leetcode/111.二叉树的最小深度/minDepth_test.go

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package _11_二叉树的最小深度
2+
3+
import "testing"
4+
5+
func Test_minDepth(t *testing.T) {
6+
type args struct {
7+
root *TreeNode
8+
}
9+
tests := []struct {
10+
name string
11+
args args
12+
want int
13+
}{
14+
{},
15+
}
16+
for _, tt := range tests {
17+
t.Run(tt.name, func(t *testing.T) {
18+
if got := minDepth(tt.args.root); got != tt.want {
19+
t.Errorf("minDepth() = %v, want %v", got, tt.want)
20+
}
21+
})
22+
}
23+
}

‎leetcode/222.完全二叉树的节点个数/countNodes.go

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package _22_完全二叉树的节点个数
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+
12+
type TreeNode struct {
13+
Val int
14+
Left *TreeNode
15+
Right *TreeNode
16+
}
17+
18+
func countNodes(root *TreeNode) int {
19+
if root == nil {
20+
return 0
21+
}
22+
var (
23+
q []*TreeNode
24+
c int
25+
)
26+
27+
q = append(q, root)
28+
29+
for len(q) != 0 {
30+
l := len(q)
31+
for i := 0; i < l; i++ {
32+
node := q[0]
33+
q = q[1:]
34+
c++
35+
if node.Left != nil {
36+
q = append(q, node.Left)
37+
}
38+
if node.Right != nil {
39+
q = append(q, node.Right)
40+
}
41+
}
42+
}
43+
44+
return c
45+
}

‎leetcode/222.完全二叉树的节点个数/countNodes_test.go

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
package _22_完全二叉树的节点个数
2+
3+
import "testing"
4+
5+
func Test_countNodes(t *testing.T) {
6+
type args struct {
7+
root *TreeNode
8+
}
9+
tests := []struct {
10+
name string
11+
args args
12+
want int
13+
}{
14+
{name: `输入：root = [1,2,3,4,5,6]
15+
输出：6`, args: args{root: &TreeNode{
16+
Val: 1,
17+
Left: &TreeNode{
18+
Val: 2,
19+
Left: &TreeNode{
20+
Val: 4,
21+
Left: nil,
22+
Right: nil,
23+
},
24+
Right: &TreeNode{
25+
Val: 5,
26+
Left: nil,
27+
Right: nil,
28+
},
29+
},
30+
Right: &TreeNode{
31+
Val: 3,
32+
Left: &TreeNode{
33+
Val: 6,
34+
Left: nil,
35+
Right: nil,
36+
},
37+
Right: nil,
38+
},
39+
}}, want: 6},
40+
}
41+
for _, tt := range tests {
42+
t.Run(tt.name, func(t *testing.T) {
43+
if got := countNodes(tt.args.root); got != tt.want {
44+
t.Errorf("countNodes() = %v, want %v", got, tt.want)
45+
}
46+
})
47+
}
48+
}

‎leetcode/25.K 个一组翻转链表/reverseKGroup.go renamed to ‎leetcode/25.K个一组翻转链表/reverseKGroup.go

Lines changed: 18 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,6 @@
1-
package _5_K_个一组翻转链表
1+
package _5_K个一组翻转链表
2+
3+
import "fmt"
24

35
/**
46
* Definition for singly-linked list.
@@ -17,29 +19,32 @@ func reverseKGroup(head *ListNode, k int) *ListNode {
1719
hair := &ListNode{Next: head}
1820
pre := hair
1921

20-
for head != nil {
21-
tail := pre
22+
var left, right = pre, pre
23+
for left != nil {
2224
for i := 0; i < k; i++ {
23-
tail = tail.Next
24-
if tail == nil {
25+
right = right.Next
26+
if right == nil {
2527
return hair.Next
2628
}
27-
2829
}
29-
tmp := tail.Next
30-
head, tail = reverseLinkedList(head, tail)
31-
pre.Next = head
32-
tail.Next = tmp
33-
pre = tail
34-
head = tail.Next
30+
next := right.Next
31+
left = left.Next
32+
fmt.Println(left, right)
33+
newLeft, newRight := reverseLinkedList(left, right)
34+
// 修改反转的指针
35+
left.Next = newLeft
36+
newRight.Next = next
37+
// 移动下一位处理
38+
left = newRight
39+
right = newRight.Next
3540
}
3641

3742
return hair.Next
3843
}
3944

4045
func reverseLinkedList(head, tail *ListNode) (*ListNode, *ListNode) {
4146
var pre, cur = tail.Next, head
42-
for cur != nil {
47+
for pre != tail {
4348
tmp := cur.Next
4449
cur.Next = pre
4550
pre = cur

0 commit comments

Comments
 (0)
0