【剑指offer】q50：树节点最近的祖先

#@ 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

由于在getPath函数里，我们获得的路径是从root開始的，即root为path列表的第一个结点。那么我们就从root開始，一次比較，找到最后一个相等的。就是二者近的共同祖先。

秒客网

【剑指offer】q50：树节点最近的祖先

相关文章