leetcode热题100. 二叉树的最近公共祖先

这篇具有很好参考价值的文章主要介绍了leetcode热题100. 二叉树的最近公共祖先。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

题目

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

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

示例 1:
leetcode热题100. 二叉树的最近公共祖先,算法,leetcode热题100,leetcode,算法,后端,python,hot100,数据结构

输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出:3
解释:节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2:
leetcode热题100. 二叉树的最近公共祖先,算法,leetcode热题100,leetcode,算法,后端,python,hot100,数据结构

输入: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 均存在于给定的二叉树中。

解题方法

声明一个字典,记录所有节点的父节点,然后用一个set集合记录p的路径,p不断向上走,直到走到根节点
然后从q出发往上,当p的路径与q的路径第一次发生交汇,说明我们找到了他们两者的最近公共父节点

复杂度

时间复杂度:

整体遍历了一次,时间复杂度: O ( n ) O(n) O(n)

空间复杂度:

使用了set集合记录路径,最坏情况下记录了所有节点,空间复杂度: O ( n ) O(n) O(n)

Code

# 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':
        global d
        d = dict()
        def dfs(root):
            if root.left:
                d[root.left.val] = root
                dfs(root.left)
            if root.right:
                d[root.right.val] = root
                dfs(root.right)
        
        dfs(root)

        # print(d)

        s = set()
        while p:
            s.add(p.val)
            if p.val not in d.keys():
                break
            p = d[p.val]

        while q:
            if q.val in s:
                return q
            q = d[q.val]

        return root

解题方法2

先序遍历所有节点,

  • 如果当前节点为空或者p,q则返回当前节点,在接受这些返回的栈帧中做一些逻辑判断
  • 如果这个left不存在,则说明左边没有p,q,则返回right,注意此时right可以有p,q,也可能没有,但是无论有无,都不影响我们这一栈帧向上的返回;
  • 如果left不是空,但是right是空,说明p或者q或者p,q都在左边节点,所以要返回left到更上一层r
  • 如果left和right都不为空,说明pq就在左右节点中,返回root到上面栈帧

复杂度2

时间复杂度:

便利了一遍: O ( n ) O(n) O(n)

空间复杂度:

栈空间为n, 示例: O ( n ) O(n) O(n)文章来源地址https://www.toymoban.com/news/detail-805866.html

Code2

# 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 or root == p or root == q: return root

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

        if not left : return right
        if not right: return left

        return root

到了这里,关于leetcode热题100. 二叉树的最近公共祖先的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法与数据结构】236、LeetCode二叉树的最近公共祖先

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 : 根据定义,最近祖先节点需要遍历节点的左右子树,然后才能知道是否为最近祖先节点。 那么这种需求是先遍历左右节点,然后遍历中间节点,属于左右中的后序遍历模式 。因此

    2024年02月09日
    浏览(37)
  • DAY23:二叉树(十三)二叉树的最近公共祖先+二叉搜索树的最近公共祖先

    一定要仔细看 提示 ,二叉树 数值不重复 ,意味着后序遍历不会存在两边找到了同个元素的情况 本题需要进一步理解后序遍历, 可以认为后序遍历在\\\"深入\\\"到每个子树的最深层之后,才开始\\\"回溯\\\"并访问节点 。 在某种意义上,这可以被视为从下往上的遍历方式 , 但需要注

    2024年02月09日
    浏览(43)
  • 【Leetcode60天带刷】day21二叉树——530.二叉搜索树的最小绝对差 ,501.二叉搜索树中的众数 ,236. 二叉树的最近公共祖先

    530. 二叉搜索树的最小绝对差 给你一个二叉搜索树的根节点  root  ,返回  树中任意两不同节点值之间的最小差值  。 差值是一个正数,其数值等于两值之差的绝对值。 示例 1: 示例 2: 提示: 树中节点的数目范围是  [2, 104] 0 = Node.val = 105 那么二叉搜索树采用中序遍历,

    2024年02月10日
    浏览(46)
  • 【Leetcode】二叉树的最近公共祖先,二叉搜索树转换成排好序的双向链表,前序遍历与中序遍历构造二叉树

    二叉树的最近公共祖先  观察上图,节点1和节点4的最近公共祖先是3,这是不是很像相交链表的问题,关于相交链表,曾经我在另一篇文章里写到过,读者可以参考:反转链表 合并链表 相交链表 但是要转换成相交链表,就要从后向前遍历,如果节点中还存在一个指针,指向

    2024年02月14日
    浏览(36)
  • 力扣236——二叉树的最近公共祖先

    祝大家新年快乐呀,虽这段时间正值过年,但是我们不要忘记停下学习的脚步。今天我们一起看一到力扣上的经典二叉树OJ题,求二叉树两个结点最近的公共祖先。 https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/ 链接给大家放在这里啦,大家一点即达 首先我们

    2024年02月20日
    浏览(40)
  • 【数据结构】二叉树篇|超清晰图解和详解:二叉树的最近公共祖先

    博主简介: 努力学习的22级计算机科学与技术本科生一枚🌸 博主主页: @是瑶瑶子啦 每日一言🌼: 你不能要求一片海洋,没有风暴,那不是海洋,是泥塘——毕淑敏 🔗236. 二叉树的最近公共祖先 注意:祖先是 包括自身 的! 🍊首先要明白,当 root为p,q的最近祖先节点 ,只

    2024年02月12日
    浏览(51)
  • Java——二叉树的最近公共祖先及二叉搜索树介绍

    目录 二叉树的最近公共祖先 题目  思路一:如果给定的是一颗二叉搜索树, 思路二:假设是孩子双亲表示法  二叉搜索树 定义Node类 查找 删除 插入 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点

    2023年04月08日
    浏览(36)
  • 【代码随想录day21】二叉树的最近公共祖先

    给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。” 这题的难点在于: 如何建

    2024年02月15日
    浏览(41)
  • 力扣第236题——二叉树的最近公共祖先 (C语言题解)

    给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大( 一个节点也可以是它自己的祖先 )。” 示例 1: 示例 2: 示例

    2024年01月20日
    浏览(39)
  • LeetCode235. 二叉搜索树的最近公共祖先

    235. 二叉搜索树的最近公共祖先 一、题目 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大( 一个节点也可以是

    2024年02月12日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包