# 68.1 二叉查找树
# 题目链接
Leetcode : 235. Lowest Common Ancestor of a Binary Search Tree
# 解题思路
func getPath(root, target *TreeNode) (path []*TreeNode) {
node := root
for node != target {
path = append(path, node)
if target.Val < node.Val {
node = node.Left
} else {
node = node.Right
}
}
path = append(path, node)
return
}
func lowestCommonAncestor(root, p, q *TreeNode) (ancestor *TreeNode) {
pathP := getPath(root, p)
pathQ := getPath(root, q)
for i := 0; i < len(pathP) && i < len(pathQ) && pathP[i] == pathQ[i]; i++ {
ancestor = pathP[i]
}
return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 68.2 普通二叉树
# 题目链接
Leetcode : 236. Lowest Common Ancestor of a Binary Tree