二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
示例二叉树
如图：节点2和8的最近公共祖先是6，节点2和4的最近公共祖先是2。
公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
题解
首先很自然地想到遍历两次二叉搜索树，搜索给定节点，然后对比遍历路径中的节点，找到深度最深的公共节点就行。Python代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def get_route(real_root, p):
route = []
root = real_root
while root.val != p.val:
route.append(root)
if root.val < p.val:
root = root.right
else:
root = root.left
route.append(p)
return route
p_route = get_route(root, p)
q_route = get_route(root, q)
ancestor = None
for p in p_route:
if p in q_route:
ancestor = p
return ancestor
|
也可以考虑将这两个节点放在一起遍历。从根节点开始遍历：
如果当前节点的值大于 p 和 q 的值，说明p 和 q应该在当前节点的左子树；如果当前节点的值小于 p 和 q 的值，说明 p 和 q 应该在当前节点的右子树。
如果当前节点的值不满足上述两条要求，那么说明当前节点就是「分岔点」。此时，p 和 q 要么在当前节点的不同的子树中，要么p、q中的一个就是当前节点。
1
2
3
4
5
6
7
8
9
| ancestor = root
while True:
if p.val < ancestor.val and q.val < ancestor.val:
ancestor = ancestor.left
elif p.val > ancestor.val and q.val > ancestor.val:
ancestor = ancestor.right
else:
break
return ancestor
|