关注Java领域相关技术 记录有趣的事情

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

US-B.Ralph
US-B.Ralph
2020-09-27

问题地址

LeetCode每日一题/2020-09-27

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

问题描述

规则

  • 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
    • 百度百科 中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
    • 例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

示例

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

说明

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

解析

解题思路

  • 要充分题目条件：
    • 所有节点的值唯一；
    • 二叉搜索树，左子树永远比根节点小，右子树永远比根节点大；
  • 对p、q进行排序，根据p、q、root值大小关系分情况讨论如下：
    • p等于q:
if (p.val == q.val) {
    if (contains(root, p)) return p;
    return null;
}

- p、q均小于root，格局题目要求找到最近的公共祖先，故需要递归遍历root.left:

if (p.val < root.val && q.val < root.val) {
    if (!contains(root, p) || !contains(root, q)) return null;
    return lowestCommonAncestor(root.left, p, q);
}

- p、q均大于root，根据题目要求找到最近的公共祖先，故需要递归遍历root.right:

if (p.val > root.val && q.val > root.val) {
    if (!contains(root, p) && !contains(root, q)) return null;
    return lowestCommonAncestor(root.right, p, q);
}

- p小于rooti且q大于root，此时只要root包含p、q，那么root就是p和q的最近公共祖先:

if (p.val < root.val && q.val > root.val) {
    if (contains(root, p) && contains(root, q)) return ans;
    return null;
}

- p或者q等于root，此时只要root包含p、q，那么root就是p和q的最近公共祖先:

if (p.val == root.val || q.val == root.val) {
    if (contains(root, p) && contains(root, q)) return ans;
    return null;
}

数据操作分析

  • 见思路分析

复杂度分析

  1. 时间复杂度
  2. 空间复杂度

编码实现

package fun.usb.algorithms.tree;
import org.junit.Assert;
import org.junit.Test;
/**
 * LeetCode0235
 */
public class LeetCode0235_LowestCcommonAncestorOfABinarySearchTree {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (p.val > q.val) {
            TreeNode t = p;
            p = q;
            q = t;
        }
        if (p.val == q.val) {
            if (contains(root, p)) return p;
            return null;
        }
        if (p.val < root.val && q.val < root.val) {
            if (!contains(root, p) || !contains(root, q)) return null;
            return lowestCommonAncestor(root.left, p, q);
        }

        if (p.val > root.val && q.val > root.val) {
            if (!contains(root, p) && !contains(root, q)) return null;
            return lowestCommonAncestor(root.right, p, q);
        }

        if (p.val < root.val && q.val > root.val) {
            if (contains(root, p) && contains(root, q)) return root;
            return null;
        }

        if (p.val == root.val || q.val == root.val) {
            if (contains(root, p) && contains(root, q)) return root;
            return null;
        }
        return null;
    }

    private boolean contains(TreeNode root, TreeNode p) {
        if (root == null || p == null) return false;
        if (p.val == root.val) return true;
        if (p.val < root.val) return contains(root.left, p);
        return contains(root.right, p);
    }
}
  • 上述代码中是可以进行分支合并的，合并代码如下：
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;

        if (p.val < root.val && q.val < root.val) {
            if (!contains(root, p) || !contains(root, q)) return null;
            return lowestCommonAncestor(root.left, p, q);
        }

        if (p.val > root.val && q.val > root.val) {
            if (!contains(root, p) && !contains(root, q)) return null;
            return lowestCommonAncestor(root.right, p, q);
        }
        if (contains(root, p) && contains(root, q)) return root;
        return null;
    }

官方解法

方法一：两次遍历

思路与算法：

  • 注意到题目中给出的是一棵「二叉搜索树」，因此我们可以快速地找出树中的某个节点以及从根节点到该节点的路径，例如我们需要找到节点 p：
  • 我们从根节点开始遍历；
    • 如果当前节点就是 p，那么成功地找到了节点；
    • 如果当前节点的值大于 p 的值，说明 p 应该在当前节点的左子树，因此将当前节点移动到它的左子节点；
    • 如果当前节点的值小于 p 的值，说明 p 应该在当前节点的右子树，因此将当前节点移动到它的右子节点。
    • 对于节点 q 同理。在寻找节点的过程中，我们可以顺便记录经过的节点，这样就得到了从根节点到被寻找节点的路径。

  • 当我们分别得到了从根节点到 p 和 q 的路径之后，我们就可以很方便地找到它们的最近公共祖先了。显然，p 和 q 的最近公共祖先就是从根节点到它们路径上的「分岔点」，也就是最后一个相同的节点。因此，如果我们设从根节点到 p 的路径为数组 \textit path_ p[]，从根节点到 q 的路径为数组 \textit path_ q[]，那么只要找出最大的编号 i，其满足\textit path_ p[i]=path_ q[i]

  • 那么对应的节点就是「分岔点」，即 p 和 q 的最近公共祖先就是 \textit path_ p[i]（或 \textit path_ q[i]）。

复杂度分析：

  1. 时间复杂度:O(n)，其中 n 是给定的二叉搜索树中的节点个数。上述代码需要的时间与节点 p 和 q 在树中的深度线性相关，而在最坏的情况下，树呈现链式结构，p 和 q 一个是树的唯一叶子结点，一个是该叶子结点的父节点，此时时间复杂度为 \Theta(n)。

  2. 空间复杂度：O(n)，我们需要存储根节点到 p 和 q 的路径。和上面的分析方法相同，在最坏的情况下，路径的长度为 \Theta(n)，因此需要 \Theta(n) 的空间。

编码实现

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> path_p = getPath(root, p);
        List<TreeNode> path_q = getPath(root, q);
        TreeNode ancestor = null;
        for (int i = 0; i < path_p.size() && i < path_q.size(); ++i) {
            if (path_p.get(i) == path_q.get(i)) {
                ancestor = path_p.get(i);
            } else {
                break;
            }
        }
        return ancestor;
    }

    public List<TreeNode> getPath(TreeNode root, TreeNode target) {
        List<TreeNode> path = new ArrayList<TreeNode>();
        TreeNode node = root;
        while (node != target) {
            path.add(node);
            if (target.val < node.val) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        path.add(node);
        return path;
    }
}

方法二：一次遍历

思路及算法：

  • 在方法一中，我们对从根节点开始，通过遍历找出到达节点 p 和 q 的路径，一共需要两次遍历。我们也可以考虑将这两个节点放在一起遍历。
  • 整体的遍历过程与方法一中的类似：
    • 我们从根节点开始遍历；
    • 如果当前节点的值大于 p 和 q 的值，说明 p 和 q 应该在当前节点的左子树，因此将当前节点移动到它的左子节点；
    • 如果当前节点的值小于 p 和 q 的值，说明 p 和 q 应该在当前节点的右子树，因此将当前节点移动到它的右子节点；
    • 如果当前节点的值不满足上述两条要求，那么说明当前节点就是「分岔点」。此时，p 和 q 要么在当前节点的不同的子树中，要么其中一个就是当前节点。
  • 可以发现，如果我们将这两个节点放在一起遍历，我们就省去了存储路径需要的空间。

复杂度分析：

  1. 时间复杂度:O(n)，其中 n 是给定的二叉搜索树中的节点个数。分析思路与方法一相同。

  2. 空间复杂度：O(1)。

编码实现

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ancestor = root;
        while (true) {
            if (p.val < ancestor.val && q.val < ancestor.val) {
                ancestor = ancestor.left;
            } else if (p.val > ancestor.val && q.val > ancestor.val) {
                ancestor = ancestor.right;
            } else {
                break;
            }
        }
        return ancestor;
    }
}

精彩评论

跳转地址1：235. 二叉搜索树的最近公共祖先:【递归】【迭代】详解

递归

思路：
  • 遇到这个题目首先想的是要是能自底向上查找就好了，这样就可以找到公共祖先了，可惜二叉树只能自上向低。
  • 那么自上相下查找的话，如何记录祖先呢？
    • 做过236. 二叉树的最近公共祖先题目的同学，应该知道，只要判断一个节点的左子树里有p，右子树里有q，那么当前节点就是最近公共祖先。
    • 那么本题是二叉搜索树，二叉搜索树是有序的，那得好好利用一下这个特点。
    • 在有序树里，如果判断一个节点的左子树里有p，右子树里有q呢？
    • 其实只要从上到下遍历的时候，如果 (p->val val && cur->val val)则说明该节点cur就是最近公共祖先了。
  • 理解这一点，本题就很好解了。如图所示:
  • 在遍历二叉搜索树的时候就是寻找区间[p->val, q->val]（注意这里是左闭右闭）
  • 那么如果 cur->val 大于 p->val，同时 cur->val 大于q->val，那么就应该向左遍历。（因为我们此时不知道p和q谁大，所以两个都要判断）代码如下：
        if (cur->val > p->val && cur->val > q->val) {
            return traversal(cur->left, p, q);
        }
  • 如果 cur->val 小于 p->val，同时 cur->val 小于 q->val，那么就应该向右遍历。
        } else if (cur->val < p->val && cur->val < q->val) {
            return traversal(cur->right, p, q);
        }
  • 剩下的情况，我们就找到了区间使（p->val val && cur->val val）或者是 （q->val val && cur->val val）代码如下：
        else {
            return cur;
        }
编码实现
class Solution {
private:
    TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q) {
        if (cur->val > p->val && cur->val > q->val) {
            return traversal(cur->left, p, q);
        } else if (cur->val < p->val && cur->val < q->val) {
            return traversal(cur->right, p, q);
        } else return cur;
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

        return traversal(root, p, q);
    }
};
迭代法代码
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while(root) {
            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;
    }
};
US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注

18 − 1 =