Problem: 236. 二叉树的最近公共祖先
题目
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 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)
空间复杂度:文章来源:https://www.toymoban.com/news/detail-805866.html
使用了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模板网!