def FindLCA
(node1
, node2
):
# Special cases. ifnot node1
ornot node2:
returnNone if node1
is node2:
return node1
# Get the first branch path. ancestors1
=set() while node1:
ancestors1.
add(node1
) node1
= node1.
parent
# Check if any ancestor of node2 is in the first branch path. while node2:
if node2
in ancestors1:
return node2
# Got it, the LCA. node2
= node2.
parent
# These two nodes have no common ancestor. returnNone
pathDict
={} path
=[] curr
= root
while curr
or path:
while curr:
# Go down along left branch path.
append((curr
, Dir.
Left)) if curr
in nodeSet:
pathDict
[curr
]=list(path
) nodeSet.
remove(curr
) ifnot nodeSet
ornot findAll:
return pathDict
curr
= curr.
left (curr
,dir)= path.
pop() whiledir== Dir.
Right:
# Back from right branch ifnot path:
return pathDict
(curr
,dir)= path.
pop() path.
append((curr
, Dir.
Right))# Trun to right from left curr
= curr.
right
def FindLCA
(root
, node1
, node2
):
# Special cases. ifnot root
ornot node1
ornot node2:
returnNone if node1
is node2:
return node1
# Try to find the two nodes in the tree, and get their branch paths. nodeSet
=set([node1
, node2
]) pathDict
= FindNodes
(root
, nodeSet
) if nodeSet:
returnNone
path1
=[i
[0]for i
in pathDict
[node1
]] path2
=[i
[0]for i
in pathDict
[node2
]]
# Compare the two paths, find out the LCA. lca
=None minLen
=min(len(path1
),len(path2
)) for i
inxrange(minLen
):
if path1
[i
]isnot path2
[i
]:
break lca
= path1
[i
]
# Pulls up the lower node and makes the two nodes in the same depth. mindepth
=min(depth1
, depth2
) for i
inxrange(depth1 - mindepth
): node1
= node1.
parent for i
inxrange(depth2 - mindepth
): node2
= node2.
parent
# Finds the common ancestor. while node1
and node2:
if node1
is node2:
return node1
node1
= node1.
parent node2
= node2.
parent
def FindLCA
(root
, node1
, node2
):
nodeset
=set([node1
, node2
])# Also supports 3 or more nodes. s
=[]# A stack to help performing N-L-R traversing. lca
=None# Records the most possible least common ancestor. mindepth
= -
1# The depth of lca. while root
or s:
if root:
if root
in nodeset:
nodeset.
remove(root
) if mindepth
<0:
# Yeah, found the first node. The lca must be itself or already in s. lca
= root
mindepth
=len(s
) ifnot nodeset:
break s.
append(root
) root
= root.
left else:
root
= s.
pop() if mindepth
>len(s
):
lca
= root
mindepth
=len(s
) root
= root.
right returnNoneif nodeset
else lca
转播
2012年04月02日 22:10
如果二叉树结点结构中有父指针，那也可以使用更节省空间的方法，就是先计算出两个结点各自的深度，如果深度不同，则将较靠下的一个结点拉上去，直到两个结点在同一深度处。然后同步向根结点前进，首次相遇时则为最小公共祖先。示意代码（python 2.7）如下：
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Special cases.
if not node1 or not node2:
return None
if node1 is node2:
return node1
# Gets each node's depth.
depth = lambda node: depth (node. parent ) + 1 if node else 0
depth1 = depth (node1 )
depth2 = depth (node2 )
# Pulls up the lower node and makes the two nodes in the same depth.
mindepth = min (depth1 , depth2 )
for i in xrange (depth1 - mindepth ): node1 = node1. parent
for i in xrange (depth2 - mindepth ): node2 = node2. parent
# Finds the common ancestor.
while node1 and node2:
if node1 is node2: return node1
node1 = node1. parent
node2 = node2. parent
return None
2012年04月05日 14:50
时间复杂度O(h)，设h是二叉树的深度。空间复杂度O(1)。
2012年04月05日 23:31
如果二叉树结点结构中没有父指针，那也可以不缓存指定结点的整条分支路径，而只需要在遍历查找的时候做点儿小小的改动。关于遍历二叉树可以参考后面的一篇文章：程序基本功之遍历二叉树。这里我将在非递归的前序（N-L-R）遍历基础上修改得到求LCA的程序。
为什么用前序遍历？
首先考察一下LCA的特性，只有两种可能：
对于第一种可能，前序遍历时首先找到的结点就是LCA，剩下的事情就是确定第二个结点在它下面。中序和后序也都可以做，但没有这么美妙。
对于第二种可能，假设在前序遍历过程中，首先找到了一个结点（比如下面的H），根据非递归前序遍历的算法特性，这时候栈里一定是依次存储了结点A（根节点）、B、D、G（请自行思考为什么没有C、E、F），再结合LCA的特性，很容易发现，LCA要么是H自身（对应于上面第一种情况），要么就只能是A、B、D或G。剩下的事情就太美妙，继续遍历二叉树，直到找到另外一个结点。这时候看看A、B、D、G和H中还有谁在栈里，最靠下的那个就是LCA。怎么判定谁在栈里？怎么判定最靠下？用辅助变量呗。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/
B
/
C
\
D
/
E
\
F
\
G
/
H
示意程序代码：
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
nodeset = set ( [node1 , node2 ] ) # Also supports 3 or more nodes.
s = [ ] # A stack to help performing N-L-R traversing.
lca = None # Records the most possible least common ancestor.
mindepth = - 1 # The depth of lca.
while root or s:
if root:
if root in nodeset:
nodeset. remove (root )
if mindepth < 0:
# Yeah, found the first node. The lca must be itself or already in s.
lca = root
mindepth = len (s )
if not nodeset:
break
s. append (root )
root = root. left
else:
root = s. pop ( )
if mindepth > len (s ):
lca = root
mindepth = len (s )
root = root. right
return None if nodeset else lca
如果与非递归前序遍历的程序比较一下，就会发现改动其实非常小。（请直接忽略上面正文中的代码）
这段程序时间复杂度都是O(n)，空间复杂度是O(h)，这些都是遍历二叉树所需的时间和空间消耗。在遍历之外，就只剩下常数量的时空开销了。
原文地址：http://www.gocalf.com/blog/least-common-ancestor.html