剑指 Offer 68 - II. 二叉树的最近公共祖先

DayNightStudy

共 3297字,需浏览 7分钟

 ·

2021-01-30 23:11

剑指 Offer 68 - II. 二叉树的最近公共祖先


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


百度百科中最近公共祖先的定义为:“对于有根树 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)。

运行结果

浏览 16
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报