本文共 1603 字，大约阅读时间需要 5 分钟。

#@ root: the root of searched tree#@ nodeToFind: the tree-node to be found#@ path: the path from root to node#@@#@@ search tree referenced by root, and return the path #@@ from root to node, if node not exist, path = []#@@def getPath(root, nodeToFind, path):	if ( None == root or None == nodeToFind):		return False	# case 1: current root == node, so insert to path	if root == nodeToFind:		path.insert(0, root)		return True 	# search in left barch and right branch	bFindInLeft = False	bFindInRight = False	if root.left:		bFindInLeft = getPath(root.left, nodeToFind, path)	if False == bFindInLeft and root.right :		bFindInRight = getPath(root.right, nodeToFind, path)	# case 2: nodeToFind in subtree of root, insert root 	if bFindInLeft or bFindInRight:		path.insert(0, root)		return True	return False

函数的功能是在root 表示的树中查找nodeToFind 结点，若找到，则在返回的时候，将路径结点加入到path中，关于树的遍历有三种，这里我们使用后序遍历，目的是在知道所有情况后，再对root进行处理，因为当前的结点root应不应该加入到路径path中，不仅跟当前的结点root有关，还跟它的子结点有关，也就是若当前结点就是要找的结点，那么将当前结点加入是没有问题的，但是即使当前结点不是要查找的结点，而其子树中有查找结点时，当前结点也是要加入到路径中去的。这样就不用每次都将结点插入，条件不满足时还要进行结点的pop。

def getClosetParent(root, node1, node2):	path1 = []; path2 = []	if None == root or None == node1 or None == node2:		return None	#get the path from root to node1 and node2	getPath(root, node1, path1)	getPath(root, node2, path2)	# find closet parent of node1 and node2	shorPathLen = min( len(path1), len(path2) )	for i in range(1, shorPathLen):		if path1[ i ] != path2[ i ] and \			path1[ i - 1 ] == path2[ i - 1 ]:			return path1[ i - 1 ]	return None

转载地址：http://numji.baihongyu.com/