LCA---Lowest common ancestor

cooxer 发布于2019-08-14 17:08 / 895人阅读

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

在root为根的二叉树中找A,B的LCA:
如果找到了就返回这个LCA
如果只碰到A，就返回A
如果只碰到B，就返回B
如果都没有，就返回null

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param root: The root of the binary search tree.
     * @param A and B: two nodes in a Binary.
     * @return: Return the least common ancestor(LCA) of the two nodes.
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
        
         //三种情况： 都在左子树中， 都在右子树中， 左右分别
        //在二叉树的左右子树找node1和node2， 找到及返回， 根据left和right是否存在内容决定最低公共祖先
        if (root == null || root == node1 || root == node2){
            return root;
        }
        
        TreeNode left = lowestCommonAncestor(root.left, node1, node2);
        TreeNode right = lowestCommonAncestor(root.right, node1, node2);
        
        if (left != null && right != null){
            return root;
        }
        
        if (left != null){
            return left; 
        }
        if (right != null){
            return right;
        }
        else{
            return null;
        }
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        //终止条件， 找到node1或者node2，或者到null node， 就return
        // if (root == null || root == node1 || root == node2) {
        //     return root;
        // }
        
        // Divide （在left child和right child里面找node1和2）
        // TreeNode left = lowestCommonAncestor(root.left, node1, node2);
        // TreeNode right = lowestCommonAncestor(root.right, node1, node2);
        
        // Conquer  
        // if (left != null && right != null) {
        //     return root;
        // } 
        // if (left != null) {
        //     return left;
        // }
        // if (right != null) {
        //     return right;
        // }
        // return null;            //当left sub和right sub都没有n1或n2
    }
}

GPU云服务器云服务器 Ancestor commonly Common commons

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

转载请注明本文地址：https://www.ucloud.cn/yun/66444.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
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
贡献一个 Laravel 树形结构管理包 ClosureTable

摘要：优雅的树形数据结构管理包基于模式设计欢迎不吝优雅的树形数据设计模式数据和结构分表操作数据不影响结构一个操作简单无需修改表兼容旧数据完善的树操作方法支持生成树形数据支持多棵树并存多个根支持节点树修复支持软删除依赖关于将树中每个节点与其后代节点 About 优雅的树形数据结构管理包,基于Closure Table模式设计. github 欢迎不吝Star Features 优雅的树形数据...

aikin 2019-06-28 14:16 评论0 收藏0
React Event 实现原理

摘要：为组建的实例化对象为组件的唯一标识为组建的实例化对象为事件名称为我们写的回调函数，也就是列子中的在每个中只实例化一次。 React 元素的事件处理和 DOM元素的很相似。但是有一点语法上的不同: React事件绑定属性的命名采用驼峰式写法，而不是小写。如果采用 JSX 的语法你需要传入一个函数作为事件处理函数，而不是一个字符串(DOM元素的写法) 并且 React 自己内部实现了...

xiguadada 2019-08-22 18:50 评论0 收藏0