236. 二叉树的最近公共祖先 [medium]

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

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

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

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

通过次数121,893 | 提交次数186,508

Third Try

2020-09-21

按后续遍历的思路来考虑问题，比second try中清晰了不少，不过还是first try中的backtrack查找路径来得更直接。

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':

        def postorder_dfs(root, p, q):
            """
            后续遍历查找，看左子树和右子树是否包含目标target
            如果左边和右边都包含，则顶部节点就是lca
            如果只有左节点或右节点包含，说明p/q中某个就是lca
            """
            if not root:
                return None 
            if root == p or root == q:
                return root 
            lft = postorder_dfs(root.left, p, q)
            rt = postorder_dfs(root.right, p, q)
            if lft and rt:
                return root
            return lft or rt  

        return postorder_dfs(root, p, q)
            

执行用时：76 ms, 在所有 Python3 提交中击败了97.79%的用户
内存消耗：25.8 MB, 在所有 Python3 提交中击败了19.67%的用户

Second Try

2020-09-21

看题解了解的使用dfs递归的方式来查找判断lca节点，有点绕一时很难想出来。这里lowestCommonAncestor函数的用法，除了用来查找lca，就是用来找到是否节点树中包含了p和q，感觉用法都混淆在一起了。

还是没有first try里面用backtrack暴力递归出root节点到目标节点路径然后判断来得直接。

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':

        # 这个只是起始查找条件，并不代表公共节点本身
        # 代表在子树里面找到了p/q节点，返回该p/q节点
        if root == p or root == q:
            return root 
        
        if not root:
            return None 

        lft = self.lowestCommonAncestor(root.left, p, q)
        rt = self.lowestCommonAncestor(root.right, p, q)

        # 如果在左右子树都能找到p/q，则这个公共节点就是root
        # 可以看到之前返回的lft和rt，与真正要查找的lca可能并无关联
        if lft and rt:  
            return root 
        
        # 剩下的表明只在一边子树里找到某个节点，那么这个节点就是公共节点本身
        return lft or rt 

执行用时：88 ms, 在所有 Python3 提交中击败了74.73%的用户
内存消耗：23.3 MB, 在所有 Python3 提交中击败了85.70%的用户

First Try

2020-09-20

第一想法是遍历整棵树找到并标记所有公共祖先，然后找到深度最深的，但是有点无从下手。

还好想到0235二叉搜索树中查找最近公共节点的方法，直接找到从根节点到目标节点的路径，然后找重叠部分即可。

于是思路变得很清晰简单了，深度遍历找到目标值，然后把路径复制下来进行比较即可。

这题目缩写为LCA，是非常常见的面试题，竟然还有没有练习过的套路题。

# 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':
        # 遍历整棵树找出所有公共祖先，然后找到深度最深的？
        # 还是找到从顶点到p和q的路径，然后找重合

        def dfs(node, target_p, target_q, path, reserve):
    
            if node == target_p:
                reserve["p"] = path[:]
            elif node == target_q:
                reserve["q"] = path[:]    
            
            if "p" in reserve and "q" in reserve:
                return 

            if node.left:
                path.append(node.left)
                dfs(node.left, target_p, target_q, path, reserve)
                path.pop()
            if node.right:
                path.append(node.right)
                dfs(node.right, target_p, target_q, path, reserve)
                path.pop()

        reserve = dict()
        dfs(root, p, q, [root], reserve)
        path_p, path_q = reserve["p"], reserve["q"]
        for i in range(min(len(path_p), len(path_q))):
            if path_p[i] != path_q[i]:
                return path_p[i - 1]
        return path_p[i]

执行用时：96 ms, 在所有 Python3 提交中击败了45.11%的用户
内存消耗：26.3 MB, 在所有 Python3 提交中击败了9.14%的用户