超超不会飞

0%

LeetCode235&236-二叉树的最近公共祖先

Posted on Views: Valine:

235.二叉搜索树的最近公共祖先

题目

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

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

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

解析

该题给的是一棵二叉搜索树，利用二叉搜索树的特点——左子树小于父节点，右子树大于父节点——我们可以提前判断 p, q 位于哪个子树中。

  1. 如果 p, q 都小于父节点，最近公共祖先一定在左子树，继续递归左子树；
  2. 如果 p, q 都大于父节点，最近公共最先一定在右子树，继续递归右子树；
  3. 递归终止条件：p, q 一个大于父节点，另一个小于父节点。证明位于左右两边，此时可知最近公共祖先就是当前父节点，返回父节点。

代码

1
2
3
4
5
6
7
8
9
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root.val > p.val && root.val > q.val) {
        return lowestCommonAncestor(root.left, p, q);
    }
    if (root.val < p.val && root.val < q.val) {
        return lowestCommonAncestor(root.right, p, q);
    }
    return root;
}

时间复杂度：O(N) 遍历整棵树；

空间复杂度：O(N) 递归占用栈空间。

除了使用递归的写法，也可以改写为 while 循环的写法：

1
2
3
4
5
6
7
8
9
10
11
12
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while (root != null) {
        if (root.val > p.val && root.val > q.val) {
            root = root.left;
        } else if (root.val < p.val && root.val < q.val) {
            root = root.right;
        } else {
            return root;
        }
    }
    return null;
}

时间复杂度：O(N) 遍历整棵树；

空间复杂度：O(1) 没有其他空间占用。

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

题目

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

百度百科中最近公共祖先的定义为：“对于有根树 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。因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

解析

该题给的是一棵二叉树，我们的思路是递归遍历整棵树：

  1. 递归终止条件：如果 root 节点是空，或者等于 p 或者 q，直接返回 root 节点；
  2. 递归左子树：在左子树中查找 p 或 q，如果能找到就返回 p 或 q，找不到就返回 null；
  3. 递归右子树：在右子树中查找 p 或 q，如果找到就返回 p 或 q，找不到就返回 null；
  4. 返回值判断：
    1. 如果左子树和右子树都有返回值，证明两个节点分别位于左右两棵树，公共祖先为当前节点；
    2. 如果左子树中找不到 p 和 q，证明两个节点都在右子树，公共祖先在右子树；
    3. 如果右子树中找不到 p 和 q，证明两个节点都在左子树，公共祖先在左子树；
    4. 如果两个子树都找不到，证明找不到 p 和 q，返回 null。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) {
        return root;
    }
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left == null) {
        return right;
    } else if (right == null) {
        return left;
    } else {
        return root;
    }
}

时间复杂度：O(N) 遍历整棵树

空间复杂度：O(N) 递归占用栈空间

本文首发于我的个人博客 https://chaohang.top

作者张小超

转载请注明出处

欢迎关注我的微信公众号 【超超不会飞】，获取第一时间的更新。