Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
class Solution(object):
def lowest_common_ancestor(self, root, p, q):
if root is None or root == p or root == q:
return root
left = self.lowest_common_ancestor(root.left, p, q)
right = self.lowest_common_ancestor(root.right, p, q)
if left and right:
return root
return left or right
今天回头做这道题目的时候没做出来 后来仔细想想 发现是递归没想通 再想想这个优雅的解法的思路是有问题的。
问题在做左右子树的递归的时候， 注意看题目two given nodes in the tree， 也就是 lowest_common_ancestor 这个函数是假定p, q在这个root下的，然后递归的基本条件 if root is None or root == p or root == q： return root也是用到了这个假定，否则是不能直接返回root的；那么在做递归的时候，如果p，q不在root.left(或root.right)下我们并不是返回None,而是返回其中一个满足条件的；所以才会有很奇怪的判断if left and right:return root. 也就是根据这个函数的意义，他讲的是当p，q的LCA同时出现在了左子树和右子树的时候，那么我们返回根节点；这是不符合这函数的意义的，而我们以此做递归. 虽然整个函数的结果是对的，至少我无法列举反例... 但这个函数的递归的过程是错误的.
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
if p == q:
return p
started = False
mini, choose_node = 1000, None
stack = []
current, curdepth = root, 0
while len(stack) or current:
if current is not None:
stack.append((current, curdepth))
current = current.left
curdepth += 1
continue
node, depth = stack.pop()
if not started:
if node == p or node == q:
mini, choose_node = depth, node
started = True
else:
if depth < mini:
mini, choose_node = depth, node
if node == p or node == q:
return choose_node
current = node.right
curdepth = depth
思路是做一个欧拉回路（inorder traversal), 没用递归， 递归过不了。用了iterative的方式，空间和时间复杂度和递归是一样的， 然而确击败97%。。。。思路来自引申1， 不同的是我们只需要找一次 所以在直接按找最小值的方式做就可以了。
引申
这个LCA的问题能够引申出一些好玩的应用：