ACM 选手图解 LeetCode 二叉树的最近公共祖先

简介: ACM 选手图解 LeetCode 二叉树的最近公共祖先

大家好呀,我是帅蛋。


今天解决二叉树的最近公共祖先很多同学在看到这个题目的时候,可能第一反应就是“卧槽?这个我能会?”。


还没开始就先把自己劝退了。

640.jpg


但是现在二叉树讲到现在,已经做了这么多题,你只要是好好跟下来的,其实只要不是特别难的题,仔细分析分析就发现解法都似曾相识。


话不多说,让我们赶紧开始~

640.png



 LeetCode 236:二叉树的最近公共祖先



题意


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


最近公共祖先:对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的最先且 x 的深度尽可能的大(一个节点也可以是它自己的祖先)。


示例


输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

输出:5

解释:节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

640.png


提示


  • 树中节点数目在范围 [2, 10^5] 内。
  • -10^9 <= Node.val <= 10^9
  • 所有的 Node.val 互不相同。
  • p != q
  • p 和 q 均存在于给定的二叉树中。


题目解析


难度中等,超级经典的题目!我想先从概念入手给大家做个剖析。


首先我们来看什么是祖先。


祖先其实就是从根节点到当前节点所经过的所有节点,以下图为例:

640.png


根据概念,对于节点 7 的祖先其实是 3、5、2、7。


然后我们再来看最近公共祖先的概念,我感觉官方在问题描述中对于这个概念介绍的有点难懂...


最近公共祖先,我感觉你们就记住,对于节点 p 和 q 来说,如果 node 为其最近公共祖先,那么 node 的左孩子和右孩子一定不是 p 和 q 的公共祖先


比如对于上图, p = 7、q = 0 来说,3 就是 p 和 q 的最近公共祖先(3 的左孩子 5 和右孩子 1 都不是 p 和 q 的公共祖先)。

640.png


根据这个我们可以得出,如果节点 node 为 p 和 q 的最近公共祖先,那么会有 3 种情况:


  • p 和 q 分别在节点 node 的左右子树中。
  • node 即为节点 p,q 在节点 p 的左子树或右子树中。
  • node 即为节点 q,p 在节点 q 的左子树或者右子树中。


这样我们可以使用递归法解决。


既然是用递归法,那还是按照往常,祭出递归二步曲:


(1) 找出重复的子问题。


这里的重复子问题就很简单,就是递归左子树,递归右子树,然后处理逻辑。

# 递归左右子树,保存递归结果
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)


你看这种先左子树,再右子树,最后处理节点的顺序,典型的后序遍历


(2) 确定终止条件。


对于本题来说,终止条件还是有点多的。


我们在递归 left 和 right 之后:


如果 left 和 right 都非空,那证明 p 和 q 一边一个,那么最近公共祖先就是 root,直接返回 root。

# 如果 left 和 right 都非空,那证明 p 和 q 一边一个,那么最近公共祖先就是 root
if left and right:
      return root


如果 right 为空,left 不为空,那只需要看 left。

# 如果 right 为空,只需要看 left
if left and right == None:
      return left


如果 left 为空,right 不为空,那只需要看 right

# 如果 left 为空,只需要看 right 
if left == None and right:
      return right


如果都为空,那就直接返回空。

# 如果都为空,返回空
if left == None and right == None:
    return None


这两点确定好了,最后的代码也就出来了。


代码实现


Python 代码实现

# 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 == None:
            return None
        # 如果 root 等于 p 或者 q,那最近公共祖先一定是 p 或者 q
        if root == p or root == q:
            return root
        # 递归左右子树,保存递归结果
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        # 如果 left 和 right 都非空,那证明 p 和 q 一边一个,那么最近公共祖先就是 root
        if left and right:
            return root
        # 如果 right 为空,只需要看 left
        if left and right == None:
            return left
        # 如果 left 为空,只需要看 right 
        if left == None and right:
            return right
        # 如果都为空,返回空
        if left == None and right == None:
            return None



Java 代码实现


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 当前节点为空,直接返回空
        if(root == null){
            return null;
        }
        // 如果 root 等于 p 或者 q,那最近公共祖先一定是 p 或者 q
        if(root == p || root == q){
            return root;
        }
        // 递归左右子树,保存递归结果
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 如果 left 和 right 都非空,那证明 p 和 q 一边一个,那么最近公共祖先就是 root
        if(left != null && right != null){
            return root;
        }
        // 如果 right 为空,只需要看 left
        else if(left != null && right == null){
            return left;
        }
        // 如果 left 为空,只需要看 right
        else if(left == null && right != null){
            return right;
        }
        // 如果都为空,返回空
        else{
            return null;
        }
    }
}


本题解,在递归过程中最坏情况下每个节点都被遍历到,
时间复杂度为 O(n)


此外在递归过程中调用了额外的栈空间,栈的大小取决于二叉树的高度,二叉树最坏情况下的高度为 n,所以空间复杂度为 O(n)



图解二叉树的最近公共祖先到这就结束辣,你看我们只需要从概念入手,一点点的剖析,解法就出来了。


还是老生常谈的那句话,题目的解决都是从我们过去学过的知识中寻找办法

今天就到这了,记得帮我点赞 + 在看 + 转发一条龙呀,爱你们~


我是帅蛋,我们下次见!

相关文章
|
1月前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
19 2
|
1月前
【LeetCode 44】235.二叉搜索树的最近公共祖先
【LeetCode 44】235.二叉搜索树的最近公共祖先
17 1
|
1月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
19 0
|
1月前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
14 0
|
1月前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
16 0
|
1月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
16 0
|
1月前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
16 0
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
57 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
114 2