LeetCode 236. 二叉树的最近公共祖先——Python实现(递归，哈希表)

1、直接用递归的方法

     使用递归的方法，找出二叉树中两个节点的最近公共祖先，分析如下：

      对于两个节点p和q的公共祖先r，他们要么在r的同一边，要么在这个节点的两边，因此，只要满足这两个条件即可，也就是说： 只要 f(r.child, p) and f(r.child,q) 成立，这个r就可能是它俩的祖先。换一个角度说，r有两条支线，现在不管p和 q在哪条支线，只要两条支线都为真(即包含目标节点)，并且有一个交集，那这个交集这就是公共祖先。 这样的话，我们只要通过 p 和 q 一路标记他们经过的路径，然后如果两个标记在某一个节点相遇了，那这样就可以找出最近公共祖先了。

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 如果已经访问到根节点都没找到相应的目标节点，那么说明这条线应该被被标记为None，这条线就停止计算
        # 如果到某一个节点，刚好是目标节点，则返回目标节点(不为空)，向上返回，标记这条线为有效的
        if root is None or root == p or root == q:
            return root
 
        # 上面一步是判断到达某一个节点是是否要停止该条路径向下的迭代，如果不停止的话，应该做的事就是，通过判断当前节点的两条子路径
        # 的情况，也就是子路径里是否包含目标节点，来判断当前节点向上返回的状态，下面的left和right分别为左边和右边返回的子树
        # 的状态，分别标记是否有效
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
 
        # 如果这个时候左右子路径刚好包含所有的目标节点，那么就说明这个root节点就是要找的公共子节点，直接返回这个节点即可
        if left and right:
            return root
 
        # 如果这个节点不是公共祖先，那么它就从两颗子树那继承状态，并返回给上一级
        if left:
            return left
        else:
            return right

2、官方还给出了一种解题思路，就是用哈希表实现，下面就是用hashmap实现的思路。

        用存储父节点的方式实现两个节点的最近公共祖先的查找。这个方法很直观，首先通过遍历的方式存储每个节点的父节点。 然后通过遍历的方式获取其中一个节点的所有父节点。遍历另一个节点的所有父节点，直到找到两者的交集点，即为所求的公共祖先。

这个方法相对于上面那个直接迭代判断的方法，消耗的内存资源会多一点。

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> bool:
        def dfs(root, parent):
            if root.left:
                parent[root.left.val] = root
                dfs(root.left, parent)
 
            if root.right:
                parent[root.right.val] = root
                dfs(root.right, parent)
 
        # 通过递归的方式，获取节点间父子关系的map
        parent = {}
        dfs(root, parent)
        parent[root.val] = None
 
        # 通过遍历的方式，找出其中一个目标节点到根节点的路劲
        visit_p = {}
        while p:
            visit_p[p] = True
            p = parent[p.val]
 
        while q:
            if visit_p.get(q, False):
                return q
 
            q = parent[q.val]