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

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

题目

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

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

示例 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 。因为根据定义最近公共祖先节点可以为节点本身。

示例 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)

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


目录
相关文章
|
1月前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
19 2
|
1月前
【LeetCode 44】235.二叉搜索树的最近公共祖先
【LeetCode 44】235.二叉搜索树的最近公共祖先
16 1
|
1月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
18 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.二叉树的所有路径
12 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实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
55 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
113 2