单次遍历，带权随机选取问题(一)
2012年04月02日 22:10如果二叉树结点结构中有父指针，那也可以使用更节省空间的方法，就是先计算出两个结点各自的深度，如果深度不同，则将较靠下的一个结点拉上去，直到两个结点在同一深度处。然后同步向根结点前进，首次相遇时则为最小公共祖先。示意代码(python 2.7)如下：
def FindLCA(node1, node2):
# Special cases.
ifnot node1 ornot 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日 23:31如果二叉树结点结构中没有父指针，那也可以不缓存指定结点的整条分支路径，而只需要在遍历查找的时候做点儿小小的改动。关于遍历二叉树可以参考后面的一篇文章：程序基本功之遍历二叉树。这里我将在非递归的前序(N-L-R)遍历基础上修改得到求LCA的程序。
为什么用前序遍历
首先考察一下LCA的特性，只有两种可能：
LCA就是其中的一个结点，而另一个结点是它的子孙;
两个结点分别位于LCA的左子树和右子树中。
对于第一种可能，前序遍历时首先找到的结点就是LCA，剩下的事情就是确定第二个结点在它下面。中序和后序也都可以做，但没有这么美妙。
对于第二种可能，假设在前序遍历过程中，首先找到了一个结点(比如下面的H)，根据非递归前序遍历的算法特性，这时候栈里一定是依次存储了结点A(根节点)、B、D、G(请自行思考为什么没有C、E、F)，再结合LCA的特性，很容易发现，LCA要么是H自身(对应于上面第一种情况)，要么就只能是A、B、D或G。剩下的事情就太美妙，继续遍历二叉树，直到找到另外一个结点。这时候看看A、B、D、G和H中还有谁在栈里，最靠下的那个就是LCA。怎么判定谁在栈里 怎么判定最靠下 用辅助变量呗。
示意程序代码：
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 return None if nodeset else lca
如果与非递归前序遍历的程序比较一下，就会发现改动其实非常小。(请直接忽略上面正文中的代码)
这段程序时间复杂度都是O(n)，空间复杂度是O(h)，这些都是遍历二叉树所需的时间和空间消耗。在遍历之外，就只剩下常数量的时空开销了