LC236.二叉树的最近公共祖先

思路1：DFS

• lowestCommonAncestor函数返回值：若root树中有公共祖先就返回公共祖先，否则返回p / q本身
• 那么如果左子树为空，说明全部都在右子树上，返回rchild，反之，返回lchild
• 如果两个子树都不是空的，说明分布在左右两边，返回root

  代码1：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 这里的lowestCommonAncestro函数定义得很暧昧：若root树中有公共祖先就返回祖先，否则返回 p / q 本身
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
            return None
        if root == p or root == q:
            return root
        # 以左子树根节点为根节点的树中，p q 的公共节点，若存在公共节点则返回公共节点，否则返回 p / q 本身
        lchild = self.lowestCommonAncestor(root.left, p, q)
        rchild = self.lowestCommonAncestor(root.right, p, q)
        # 如果在左子树和右子树中找到的公共节点都存在：
        # 说明两个节点分别在左子树和右子树上
        if lchild and rchild:
            return root
        elif lchild == None:
            return rchild
        else:
            return lchild
        return None

思路2：另外一种DFS

• 题解提供的思路，非常清晰
• dfs(root, p, q)表示，以root为根节点的子树，是否包含p或者q当中的至少一个，如果是则返回True，否则返回False
• 两种情况可以确定祖先
  • 如果分别在左右节点上，lchildInclude and rchildInclude同时成立
  • 一者是根节点，同时另外一者在其左子树或者右子树上

    代码2：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def __init__(self):
        self.ancestor: TreeNode() = None
    # root子树中是否含有p 和 q 两个节点中至少一个
    def dfs(self, root: TreeNode(), p: TreeNode(), q: TreeNode()) -> bool:
        if not root:
            return False
        lchildInclude = self.dfs(root.left, p, q)
        rchildInclude = self.dfs(root.right, p, q)
        # 第一种情况：分别在左右节点上
        if lchildInclude and rchildInclude:
            self.ancestor = root
        # 第二种情况：某一个是根节点
        if (root == p) and (lchildInclude or rchildInclude):
            self.ancestor = root
        elif (root == q) and (lchildInclude or rchildInclude):
            self.ancestor = root
        return lchildInclude or rchildInclude or root == p or root == q
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        self.dfs(root, p, q)
        return self.ancestor

思路3：DFS + 建立爸爸表

• 树结构的问题中，建立爸爸表是一件很重要的事情
• 所谓爸爸表，就是一个字典，其记录了每个节点的父亲是谁，fa[node] = oldNode表示node节点的爸爸是oldNode。
• 可以通过DFS的方式去建立爸爸表，然后孩子节点从下往上找爸爸，找到的位置通过vis字典去标记，第二个孩子往上走的时候，如果vis字典中已经有相关记录了，那么就说明这是一个公共祖先。
• 此方法应该是此题最最直观的想法了。

  代码3：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def __init__(self):
        self.ancestor: TreeNode() = None
        self.fa = dict()
        self.vis = set()
    def dfs(self, root: TreeNode()) -> None:
        if not root:
            return
        if root.left:
            self.fa[root.left] = root
            self.dfs(root.left)
        if root.right:
            self.fa[root.right] = root
            self.dfs(root.right)
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 建立爸爸表
        self.dfs(root)
        self.fa[root] = None
        # 叶子节点从下往上遍历
        while p != None:
            self.vis.add(p)
            p = self.fa[p]
        while q != None:
            if q in self.vis:
                return q
            q = self.fa[q]
        return root