[LintCode/LeetCode] Lowest Common Ancestor of BST/

dinfer 发布于2019-08-14 15:33 / 1674人阅读

摘要：递归左右子树，若左右子树都有解，那么返回根节点若仅左子树有解，返回左子树若仅右子树有解，返回右子树若都无解，返回。对于而言，更为简单公共祖先一定是大于等于其中一个结点，小于等于另一个结点。

Problem

Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.

The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.

Example

For the following binary tree:

LCA(3, 5) = 4

LCA(5, 6) = 7

LCA(6, 7) = 7

Note

递归左右子树，若左右子树都有解，那么返回根节点；若仅左子树有解，返回左子树；若仅右子树有解，返回右子树；若都无解，返回null。

对于BST而言，更为简单：公共祖先一定是大于等于其中一个结点，小于等于另一个结点。那么若两个结点都小于当前的root结点，完全可以继续去比较第一个比root小的结点：root.left；若两个结点都大于当前的root结点，就去比较第一个比root大的结点：root.right；否则，一定是满足一个结点小于等于root，另一个结点大于等于root的情况了，返回root即可。

For the binary search tree, the root.val must be smaller than its right children but larger than its left children. Therefore, there are three basic possible relationships among root, p and q.

p.val >= root.val && q.val <= root.val;
p.val > root.val && q.val > root.val;
p.val < root.val && q.val < root.val;

Here we ignored the situation if we switch p and q, that"s equivalent situation to the first one, of which the result is root. So we just need to dig into the 2nd and 3rd.
For the 2nd situation, replace root with root.right cause the common ancestor must be larger than root, then we can just use recursion to get the answer.
Same for the 3rd.

Solution

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
        if (root == null || root == A || root == B) return root;
        TreeNode left = lowestCommonAncestor(root.left, A, B);
        TreeNode right = lowestCommonAncestor(root.right, A, B);
        if (left != null && right != null) return root;
        if (left != null && right == null) return left;
        if (left == null && right != null) return right;
        return null;
    }
}

For BST：

public class Solution {
    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;
    }
}

专线服务 idc机房托管 Ancestor Lowest Common BST

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65850.html

[Leetcode] Lowest Common Ancestor of a Binary Tree

摘要：如果子树中有目标节点，标记为那个目标节点，如果没有，标记为。显然，如果左子树右子树都有标记，说明就已经找到最小公共祖先了。如果在根节点为的左右子树中找的公共祖先，则必定是本身。只有一个节点正好左子树有，右子树也有的时候，才是最小公共祖先。 Lowest Common Ancestor of a Binary Search Tree 最新更新请见：https://yanjia.me/zh...

Dr_Noooo 2019-08-14 12:25 评论0 收藏0
leetcode235-236 lowest common ancestor

摘要：如果左右子树返回的最低共同父节点值都不是空，说明和分别位于的左右子树，那么就是最低共同父节点。 235题-题目要求 Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST. According to the definition of L...

chadLi 2019-08-15 13:37 评论0 收藏0
LCA---Lowest common ancestor

摘要：在为根的二叉树中找的如果找到了就返回这个如果只碰到，就返回如果只碰到，就返回如果都没有，就返回三种情况都在左子树中，都在右子树中，左右分别在二叉树的左右子树找和，找到及返回，根据和是否存在内容决定最低公共祖先终止条件，找到或者，或者到，就在在root为根的二叉树中找A,B的LCA: 如果找到了就返回这个LCA 如果只碰到A，就返回A 如果只碰到B，就返回B 如果都没有，就返回null...

cooxer 2019-08-14 17:08 评论0 收藏0
FE-ES 前端数据结构与算法leedcode训练合集40题

摘要：无关知识点精通一个领域切碎知识点刻意练习反馈切题四件套审题所有解法比较时间空间复杂度加强编码测试用例数组，链表数组查询插入删除链表查询插入删除翻转链表两两翻转链表判断链表是否有环栈，队列判断合法括号栈模拟队列队列模拟栈找第大的元素 showImg(https://segmentfault.com/img/bVbqeRl?w=1600&h=1126); 无关知识点 1.精通一个领域： ...

dabai 2019-08-23 16:14 评论0 收藏0
[LintCode/LeetCode] Convert Sorted List to Balance

摘要：当链表为空时，中出现大于，返回。然后计算中点，以为界分别递归构建左右子树。顺序是，左子树根结点右子树。由于根节点是直接取构建，当前的已经被取用。所以在下一次递归构建右子树之前，要让指向。最后将和左右子树相连，返回。 Problem Given a singly linked list where elements are sorted in ascending order, conve...

Michael_Ding 2019-08-14 15:32 评论0 收藏0