剑指 Offer 68 - II. 二叉树的最近公共祖先
共 3297字,需浏览 7分钟
·
2021-01-30 23:11
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 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。因为根据定义最近公共祖先节点可以为节点本身。
题目解析
root 为 p 和 q 最近公共祖先的满足条件:
1. root 为 p,q 的 某公共祖先;
2. root.left 和 root.right 都不是 p,q 的 公共祖先;
root 为 p 和 q 最近公共祖先的分情况分析:
1. p 和 q 分别在 root 的 异侧子树(左子树 和 右子树);
2. p = root,同时,q 在 root 的左或右子树;
3. q = root,同时,p 在 root 的左或右子树;
题目解答
思路:
# step 1:判断三种情况:
# 1. not root:到达 叶子节点;
# 2. root==p or root==q :找到 对应节点
# step 2:分别 向 左右子树 递归
# step 3:root 的左 / 右子树中都不包含 p,q
# step 4:p,q 都不在 root 的 左子树上,右子树 分两种情况:
# 1. p/q 在 root 右子树 中,此时返回 right 指向 p/q;
# 2. p,q 都在 root 右子树中,此时 right 指向 最近公共祖先节点
# step 5: 也 step 4 雷同
# step 6:当 left 和 right 都不为空,说明 p 和 q 在 root 的 异侧(分别在 左右
代码展示
# 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:
'''
思路:递归法
介绍:
root 为 p 和 q 最近公共祖先的满足条件:
1. root 为 p,q 的 某公共祖先;
2. root.left 和 root.right 都不是 p,q 的 公共祖先;
root 为 p 和 q 最近公共祖先的分情况分析:
1. p 和 q 分别在 root 的 异侧子树(左子树 和 右子树);
2. p = root,同时,q 在 root 的左或右子树;
3. q = root,同时,p 在 root 的左或右子树;
思路:
# step 1:判断三种情况:
# 1. not root:到达 叶子节点;
# 2. root==p or root==q :找到 对应节点
# step 2:分别 向 左右子树 递归
# step 3:root 的左 / 右子树中都不包含 p,q
# step 4:p,q 都不在 root 的 左子树上,右子树 分两种情况:
# 1. p/q 在 root 右子树 中,此时返回 right 指向 p/q;
# 2. p,q 都在 root 右子树中,此时 right 指向 最近公共祖先节点
# step 5: 也 step 4 雷同
# step 6:当 left 和 right 都不为空,说明 p 和 q 在 root 的 异侧(分别在 左右子树),故 root 为最近公共祖先
'''
# step 1:判断三种情况:
# 1. not root:到达 叶子节点;
# 2. root==p or root==q :找到 对应节点
if not root or root==p or root==q:
return root
# step 2:分别 向 左右子树 递归
left = self.lowestCommonAncestor(root.left,p,q)
right=self.lowestCommonAncestor(root.right,p,q)
# step 3:root 的左 / 右子树中都不包含 p,q
if not left and not right:
return None
# step 4:p,q 都不在 root 的 左子树上,右子树 分两种情况:
# 1. p/q 在 root 右子树 中,此时返回 right 指向 p/q;
# 2. p,q 都在 root 右子树中,此时 right 指向 最近公共祖先节点
if left and not right:
return left
# step 5: 也 step 4 雷同
elif right and not left:
return right
# step 6:当 left 和 right 都不为空,说明 p 和 q 在 root 的 异侧(分别在 左右子树),故 root 为最近公共祖先
else:
return root
复杂度计算
时间复杂度:O(N),其中 N 是二叉树的节点数。二叉树的所有节点有且只会被访问一次,因此时间复杂度为 O(N)。
-空间复杂度:O(N),其中 N 是二叉树的节点数。递归调用的栈深度取决于二叉树的高度,二叉树最坏情况下为一条链,此时高度为 N,因此空间复杂度为 O(N)。
运行结果