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

Difficulty
Medium
Tags
二叉树
URL
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
Star
❤
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
notion imagenotion image
输入：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 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1
提示：
  • 树中节点数目在范围 [2, 105] 内。
  • 109 <= Node.val <= 109
  • 所有 Node.val 互不相同 。
  • p != q
  • p 和 q 均存在于给定的二叉树中。

法1 递归

思路 1
参考 labuladong 遇到任何递归型的问题，无非就是灵魂三问：
  1. 这个函数是干嘛的？
  1. 这个函数参数中的变量是什么的是什么？
  1. 得到函数的递归结果，你应该干什么？
首先第一个问题：这个函数是干嘛的？
描述：给该函数输入三个参数root，p，q，它会返回一个节点。
  • 情况 1，如果p和q都在以root为根的树中，函数返回的即使p和q的最近公共祖先节点。
  • 情况 2，那如果p和q都不在以root为根的树中怎么办呢？函数理所当然地返回null
  • 情况 3，那如果p和q只有一个存在于root为根的树中呢？函数就会返回那个节点。
题目说了输入的p和q一定存在于以root为根的树中，但是递归过程中，以上三种情况都有可能发生。
第二个问题：这个函数的参数中，变量是什么？
描述：函数参数中的变量是root，因为根据框架，lowestCommonAncestor(root)会递归调用root.left和root.right；至于p和q，我们要求它俩的公共祖先，它俩肯定不会变化的。
第三个问题：得到函数的递归结果，你该干嘛？
分析这个「最近公共祖先节点」有什么特点呢？刚才说了函数中的变量是root参数，所以这里都要围绕root节点的情况来展开讨论。
先想 base case，如果root为空，肯定得返回null。如果root本身就是p或者q，比如说root就是p节点吧，如果q存在于以root为根的树中，显然root就是最近公共祖先；即使q不存在于以root为根的树中，按照情况 3 的定义，也应该返回root节点。
以上两种情况的 base case 就可以把框架代码填充一点了：
TreeNodelowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 两种情况的 base case
if (root ==null)returnnull;
if (root == p || root == q)return root;

    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
}
现在就要面临真正的挑战了，用递归调用的结果left和right来搞点事情。根据刚才第一个问题中对函数的定义，我们继续分情况讨论：
情况 1，如果p和q都在以root为根的树中，那么left和right一定分别是p和q（从 base case 看出来的）直接返回root。
情况 2，如果p和q都不在以root为根的树中，直接返回null。
情况 3，如果p和q只有一个存在于root为根的树中，函数返回该节点。
思路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 lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 基线条件
        if root is None:
            return
        if root is p or root is q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:
            return root
        if left is None and right is None:
            return None
        if left is None:
            return right
        else:
            return left

法2 根据路径查找

思路
遍历二叉树，查找从根节点到目标的路径，当两个目标节点的路径都找到后，在两个路径里面找就会很容易
至于目标节点的路径 参考
🛵
257. 二叉树的所有路径
注：因为题目要求返回的是公共祖先，所以存放路径时需要存放节点
题解
# 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':
        result = []    # 存放结果的
        tree_q = []    # 辅助遍历二叉树的栈 or 队列
        path_temp = [] # 对应tree_q中每个节点的路径

        tree_q.append(root)
        path_temp.append([root])
        # 循环条件除了常规的遍历条件外，还多了判断是否已经找到两个节点的路径了
        while len(tree_q) > 0 and len(result)<2:
            node = tree_q.pop(0) # 当前节点
            path = path_temp.pop(0) # 从根节点到当前节点的路径

            # 如果是目标节点，则把路径加进去
            if node is p or node is q:
                result.append(path)
            # node不是叶子节点 ,去遍历左右子树，
			# 同时分别更新path(在node的path上新增左右节点的值)，并随左右子节点加入队列
            if node.left:
                tree_q.append(node.left)
                path_temp.append(path+[node.left])
            if node.right:
                tree_q.append(node.right)
                path_temp.append(path+[node.right])
        
        # 两个目标节点都在
        if len(result) == 2:
            i = 0
            while i < len(result[0]) and i < len(result[1]):
                if result[0][i] == result[1][i]:
                    i += 1
                else:
                    break
            return result[0][i-1]

        else:
            return None
# 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':
        result_path = [] # 存放从根节点到p q节点的路径
        path = [] # 辅助寻访路径
        stack = [] # 辅助栈
        
        stack.append(root)
        path.append([root])
        while len(stack) > 0 or len(result_path) < 2:
            node = stack.pop()
            path_temp = path.pop()
            if node == p  or node == q:
                result_path.append(path_temp)

            if node.left:
                stack.append(node.left)
                path.append(path_temp+[node.left])
            if node.right:
                stack.append(node.left)
                path.append(path_temp+[node.right])
        print(result_path[0])
        # 两个路径均已找到
        i = min(len(result_path[0]), len(result_path[1]))-1
        while i > 0:
            if result_path[0][i] is result_path[1][i]:
                return result_path[0][i]
            else:
                i -= 1