8000 feat: 2021年05月13日23:34:27 · chenshiwei-io/leetcode@c67d9d8 · GitHub
[go: up one dir, main page]
Skip to content

Commit c67d9d8

Browse files
author
chen-shiwei
committed
feat: 2021年05月13日23:34:27
1 parent 40795b3 commit c67d9d8

File tree

5 files changed

+177
-103
lines changed

5 files changed

+177
-103
lines changed

‎leetcode/235.二叉搜索树的最近公共祖先/lowestCommonAncestor.go

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
package _35_二叉搜索树的最近公共祖先
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 lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
19+
if root == nil {
20+
return root
21+
}
22+
23+
if root.Val > p.Val && root.Val > q.Val {
24+
left := lowestCommonAncestor(root.Left, p, q)
25+
if left != nil {
26+
return left
27+
}
28+
}
29+
if root.Val < p.Val && root.Val < q.Val {
30+
right := lowestCommonAncestor(root.Right, p, q)
31+
if right != nil {
32+
return right
33+
}
34+
}
35+
36+
return root
37+
}

‎leetcode/236.二叉树的最近公共祖先/lowestCommonAncestor.go

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package _36_二叉树的最近公共祖先
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 lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
19+
if root == nil || root == q || root == p {
20+
return root
21+
}
22+
23+
left := lowestCommonAncestor(root.Left, p, q)
24+
right := lowestCommonAncestor(root.Right, p, q)
25+
if left != nil && right != nil {
26+
return root
27+
}
28+
29+
if left != nil {
30+
return right
31+
}
32+
33+
return left
34+
}

‎leetcode/236.二叉树的最近公共祖先/lowestCommonAncestor_test.go

Lines changed: 106 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,106 @@
1+
package _36_二叉树的最近公共祖先
2+
3+
import (
4+
"reflect"
5+
"testing"
6+
)
7+
8+
func Test_lowestCommonAncestor(t *testing.T) {
9+
type args struct {
10+
root *TreeNode
11+
p *TreeNode
12+
q *TreeNode
13+
}
14+
tests := []struct {
15+
name string
16+
args args
17+
want *TreeNode
18+
}{
19+
{name: `输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
20+
输出：3
21+
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。`, args: args{
22+
root: &TreeNode{
23+
Val: 3,
24+
Left: &TreeNode{
25+
Val: 5,
26+
Left: &TreeNode{
27+
Val: 6,
28+
Left: nil,
29+
Right: nil,
30+
},
31+
Right: &TreeNode{
32+
Val: 2,
33+
Left: &TreeNode{
34+
Val: 7,
35+
Left: nil,
36+
Right: nil,
37+
},
38+
Right: &TreeNode{
39+
Val: 4,
40+
Left: nil,
41+
Right: nil,
42+
},
43+
},
44+
},
45+
Right: &TreeNode{
46+
Val: 1,
47+
Left: &TreeNode{
48+
Val: 0,
49+
Left: nil,
50+
Right: nil,
51+
},
52+
Right: &TreeNode{
53+
Val: 8,
54+
Left: nil,
55+
Right: nil,
56+
},
57+
},
58+
},
59+
p: &TreeNode{
60+
Val: 5,
61+
Left: &TreeNode{
62+
Val: 6,
63+
Left: nil,
64+
Right: nil,
65+
},
66+
Right: &TreeNode{
67+
Val: 2,
68+
Left: &TreeNode{
69+
Val: 7,
70+
Left: nil,
71+
Right: nil,
72+
},
73+
Right: &TreeNode{
74+
Val: 4,
75+
Left: nil,
76+
Right: nil,
77+
},
78+
},
79+
},
80+
q: &TreeNode{
81+
Val: 1,
82+
Left: &TreeNode{
83+
Val: 0,
84+
Left: nil,
85+
Right: nil,
86+
},
87+
Right: &TreeNode{
88+
Val: 8,
89+
Left: nil,
90+
Right: nil,
91+
},
92+
},
93+
}, want: &TreeNode{
94+
Val: 3,
95+
Left: nil,
96+
Right: nil,
97+
}},
98+
}
99+
for _, tt := range tests {
100+
t.Run(tt.name, func(t *testing.T) {
101+
if got := lowestCommonAncestor(tt.args.root, tt.args.p, tt.args.q); !reflect.DeepEqual(got, tt.want) {
102+
t.Errorf("lowestCommonAncestor() = %v, want %v", got, tt.want)
103+
}
104+
})
105+
}
106+
}

‎leetcode/236.二叉树的最近公共祖先_todo/lowestCommonAncestor.go

Lines changed: 0 additions & 65 deletions
This file was deleted.

‎leetcode/236.二叉树的最近公共祖先_todo/lowestCommonAncestor_test.go

Lines changed: 0 additions & 38 deletions
This file was deleted.

0 commit comments

Comments
 (0)
0