二叉树的最近公共祖先(LCA)

本文讨论求一个二叉树中两个节点的最近公共祖先的算法。这里只讨论一次性算法,对于可以高效处理多个查询的离线算法不在本文讨论范围。

二叉查找树(BST)

对于一个二叉查找树,解法简单粗暴,只需与根节点做大小比较,如果两节点都比根节点小,则从根节点的左子树继续查找;如果都比根节点大,则从根节点的右子树继续查找;如果不是这两种情况,则根节点即为LCA。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
# @param {TreeNode} root
# @param {TreeNode} p
# @param {TreeNode} q
# @return {TreeNode}
def lowestCommonAncestor(self, root, p, q):
if p.val < root.val and q.val < root.val:
return self.lowestCommonAncestor(root.left, p, q)
if p.val > root.val and q.val > root.val:
return self.lowestCommonAncestor(root.right, p, q)
return root

非二叉查找树

此时如果每个节点知道其父节点,则可以从这两个节点出发,向根节点上爬,于是各自可以看作是一条单向链表。问题转化为两个单向链表求第一个公共节点的问题。

两个单向链表求第一个公共节点

如果两个单向链表存在公共节点,则两链表会在第一个公共节点处相交,形成一个Y字形(而不可能是X形)。
这时只需要分别求出两个链表的长度,然后先从较长的那个链表开始,走出它比另一个链表长出的距离,此时再与另一链表一起往前遍历,第一次遇到相同的节点时即为两链表的第一个公共节点。

也可以先求出所有节点的父节点信息,然后用这种方法计算,代码如下:

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
28
29
30
31
32
33
34
35
36
37
38
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
# @param {TreeNode} root
# @param {TreeNode} p
# @param {TreeNode} q
# @return {TreeNode}
def lowestCommonAncestor(self, root, p, q):
# get parent links
def get_pnt(node, pnt, pntDic):
if node == None: return
pntDic[node] = pnt
get_pnt(node.left, node, pntDic)
get_pnt(node.right, node, pntDic)
pnt = {}
get_pnt(root, None, pnt)

lp, lq = 0, 0
tp, tq = p, q
while tp:
lp += 1
tp = pnt[tp]
while tq:
lq += 1
tq = pnt[tq]
tp, tq = p, q
for i in xrange(lp-lq): tp = pnt[tp]
for i in xrange(lq-lp): tq = pnt[tq]
while tp:
if tp == tq: return tp
tp = pnt[tp]
tq = pnt[tq]
return None

此外,也可以直接从根节点开始使用递归,同样可以很快的计算出LCA,递归的算法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
# @param {TreeNode} root
# @param {TreeNode} p
# @param {TreeNode} q
# @return {TreeNode}
def lowestCommonAncestor(self, root, p, q):
if root == None: return None
if root == p or root == q: return root
leftLCA = self.lowestCommonAncestor(root.left, p, q)
rightLCA = self.lowestCommonAncestor(root.right, p, q)
if leftLCA and rightLCA: return root
if leftLCA: return leftLCA
if rightLCA: return rightLCA
return None