二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

---

递归的思路

公共祖先有两种情况：
1.因为p节点和q节点都是不同且唯一的节点, p和q分别位于左和右子树，则根节点为公共祖先
2.p或者q为根节点，另一个节点在左或右子树中

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
            return root
        if root.val == p.val or root.val == q.val:
            return root
        left_node = self.lowestCommonAncestor(root.left, p, q)
        right_node = self.lowestCommonAncestor(root.right, p, q)
        if not left_node:
            return right_node
        if not right_node:
            return left_node

        if left_node and right_node:
            return root

哈希表存储父节点

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def helper(root, father_dict):
            if not root:
                return 
            if root.left:
                father_dict[root.left.val] = root
                helper(root.left, father_dict)
            if root.right:
                father_dict[root.right.val] = root
                helper(root.right, father_dict)
        if not root:
            return
        father_dict = dict()
        father_dict[root.val] = None
        helper(root, father_dict)
        path = dict()
        while p:
            path[p.val] = 1
            p = father_dict[p.val]
        
        while q:
            if q.val in path:
                return q
            q = father_dict[q.val]