leetcode235-236 lowest common ancestor

chadLi 发布于2019-08-15 13:37 / 2073人阅读

摘要：如果左右子树返回的最低共同父节点值都不是空，说明和分别位于的左右子树，那么就是最低共同父节点。

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 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.

现在有一棵搜索二叉树，这个二叉树的特点是左子树的节点一定小于根节点，而右子树的节点一定大于根节点。现在提供这棵树的根节点，并且输入两个节点，问这两个节点的最低共同父节点是谁？
最低共同父节点是指两个节点在沿父节点向上爬升时遇到的第一个共同父节点，同时它也允许父节点就是其本身，比如在上图中2和4的最低共同父节点就是2

思路和代码

这里我们因为可以根据数值来判断，需要寻找最低共同父节点的两个节点跟当前的根节点的大小比较，如果两个值都比根节点小，则最小父节点一定在左子树，二者都比它大，就在右子树。否则当前的根节点就是他们的最低共同父节点。

代码如下：这里采用递归的方式来寻找

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
         if(p.val > q.val){
             return lca(root, q, p);
         }else{
             return lca(root, p, q);
         }
     }
     
     public TreeNode lca(TreeNode root, TreeNode small, TreeNode large){
         if(root.val < small.val){
             return lca(root.right, small, large);
         }else if(root.val > large.val){
             return lca(root.left, small, large);
         }
         return root;
     }

236题将搜索树改变为一般的二叉树

236题相对于235题而言，就是将题目中的搜索树条件改变成了一般的二叉树。这时我们无法通过和根节点比较数值大小来判断最低共同父节点究竟是在左子树还是右子树还是就是当前的根节点。

这时我们先试着用穷举法来找到所有可能的情况，现在已知根节点root和两个需要查找父节点的节点p,q

p, q分别位于root的左子树和右子树： root为最低共同父节点

p, q均位于root的左子树: 继续在root.left寻找最低共同父节点

p, q均为与root的右子树: 继续在root.right寻找最低共同父节点

root==p：最低共同父节点为p或p的某个父节点

root==q：最低共同父节点为q或q的某个父节点

我们再进行汇总，如果我们在向下遍历左子树和右子树的过程中，一旦遇到p或q，则返回p或q，因为继续往下遍历的值都不会是p和q的共同父节点。如果左右子树返回的最低共同父节点值都不是空，说明p和q分别位于root的左右子树，那么root就是最低共同父节点。如果两个都为空，说明当前根节点不包含p和q。如果其中一棵子树返回的值不为空，那么就说明p和q都位于那棵子树上，且返回的值就是遍历过程中最先遇到的p或者q，也就是最低共同父节点。

代码如下：

    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 && right!=null) return root;
        return left==null ? right : left;
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

云服务器 GPU云服务器 Ancestor Lowest Leetcod LeetCode

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

转载请注明本文地址：https://www.ucloud.cn/yun/68211.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
[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
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