[Leetcode] Lowest Common Ancestor of a Binary Tree

Dr_Noooo 发布于2019-08-14 12:25 / 2516人阅读

摘要：如果子树中有目标节点，标记为那个目标节点，如果没有，标记为。显然，如果左子树右子树都有标记，说明就已经找到最小公共祖先了。如果在根节点为的左右子树中找的公共祖先，则必定是本身。只有一个节点正好左子树有，右子树也有的时候，才是最小公共祖先。

Lowest Common Ancestor of a Binary Search Tree 最新更新请见：https://yanjia.me/zh/2019/02/...

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
       /              
    ___2__          ___8__
   /              /      
   0      _4       7       9
         /  
         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

二分法 复杂度

时间 O(h) 空间 O(h) 递归栈空间

思路

对于二叉搜索树，公共祖先的值一定大于等于较小的节点，小于等于较大的节点。换言之，在遍历树的时候，如果当前结点大于两个节点，则结果在当前结点的左子树里，如果当前结点小于两个节点，则结果在当前节点的右子树里。

代码

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;
    }
}

Lowest Common Ancestor of a Binary Tree 最新更新请见：https://yanjia.me/zh/2019/02/...

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

        _______3______
       /              
    ___5__          ___1__
   /              /      
   6      _2       0       8
         /  
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

深度优先标记 复杂度

时间 O(h) 空间 O(h) 递归栈空间

思路

我们可以用深度优先搜索，从叶子节点向上，标记子树中出现目标节点的情况。如果子树中有目标节点，标记为那个目标节点，如果没有，标记为null。显然，如果左子树、右子树都有标记，说明就已经找到最小公共祖先了。如果在根节点为p的左右子树中找p、q的公共祖先，则必定是p本身。

换个角度，可以这么想：如果一个节点左子树有两个目标节点中的一个，右子树没有，那这个节点肯定不是最小公共祖先。如果一个节点右子树有两个目标节点中的一个，左子树没有，那这个节点肯定也不是最小公共祖先。只有一个节点正好左子树有，右子树也有的时候，才是最小公共祖先。

代码

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //发现目标节点则通过返回值标记该子树发现了某个目标结点
        if(root == null || root == p || root == q) return root;
        //查看左子树中是否有目标结点，没有为null
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        //查看右子树是否有目标节点，没有为null
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        //都不为空，说明做右子树都有目标结点，则公共祖先就是本身
        if(left!=null&&right!=null) return root;
        //如果发现了目标节点，则继续向上标记为该目标节点
        return left == null ? right : left;
    }
}

GPU云服务器云服务器 binary-tree binary-search-tree Ancestor Lowest

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

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

[LintCode/LeetCode] Lowest Common Ancestor of BST/

摘要：递归左右子树，若左右子树都有解，那么返回根节点若仅左子树有解，返回左子树若仅右子树有解，返回右子树若都无解，返回。对于而言，更为简单公共祖先一定是大于等于其中一个结点，小于等于另一个结点。 Problem Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the ...

dinfer 2019-08-14 15:33 评论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
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论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