成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

LCA---Lowest common ancestor

cooxer / 743人閱讀

摘要：在為根的二叉樹中找的如果找到了就返回這個(gè)如果只碰到，就返回如果只碰到，就返回如果都沒有，就返回三種情況都在左子樹中，都在右子樹中，左右分別在二叉樹的左右子樹找和，找到及返回，根據(jù)和是否存在內(nèi)容決定最低公共祖先終止條件，找到或者，或者到，就在

在root為根的二叉樹中找A,B的LCA:
如果找到了就返回這個(gè)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， 找到及返回， 根據(jù)left和right是否存在內(nèi)容決定最低公共祖先
        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;            //當(dāng)left sub和right sub都沒有n1或n2
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/66444.html

相關(guān)文章

  • [Leetcode] Lowest Common Ancestor of a Binary Tree

    摘要：如果子樹中有目標(biāo)節(jié)點(diǎn)，標(biāo)記為那個(gè)目標(biāo)節(jié)點(diǎn)，如果沒有，標(biāo)記為。顯然，如果左子樹右子樹都有標(biāo)記，說明就已經(jīng)找到最小公共祖先了。如果在根節(jié)點(diǎn)為的左右子樹中找的公共祖先，則必定是本身。只有一個(gè)節(jié)點(diǎn)正好左子樹有，右子樹也有的時(shí)候，才是最小公共祖先。 Lowest Common Ancestor of a Binary Search Tree 最新更新請見：https://yanjia.me/zh...

    Dr_Noooo 評論0 收藏0

  • [LintCode/LeetCode] Lowest Common Ancestor of BST/

    摘要：遞歸左右子樹，若左右子樹都有解，那么返回根節(jié)點(diǎn)若僅左子樹有解，返回左子樹若僅右子樹有解，返回右子樹若都無解，返回。對于而言，更為簡單公共祖先一定是大于等于其中一個(gè)結(jié)點(diǎn)，小于等于另一個(gè)結(jié)點(diǎn)。 Problem Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the ...

    dinfer 評論0 收藏0

  • leetcode235-236 lowest common ancestor

    摘要：如果左右子樹返回的最低共同父節(jié)點(diǎn)值都不是空，說明和分別位于的左右子樹，那么就是最低共同父節(jié)點(diǎn)。 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 評論0 收藏0

  • 貢獻(xiàn)一個(gè) Laravel 樹形結(jié)構(gòu)管理包 ClosureTable

    摘要：優(yōu)雅的樹形數(shù)據(jù)結(jié)構(gòu)管理包基于模式設(shè)計(jì)歡迎不吝優(yōu)雅的樹形數(shù)據(jù)設(shè)計(jì)模式數(shù)據(jù)和結(jié)構(gòu)分表操作數(shù)據(jù)不影響結(jié)構(gòu)一個(gè)操作簡單無需修改表兼容舊數(shù)據(jù)完善的樹操作方法支持生成樹形數(shù)據(jù)支持多棵樹并存多個(gè)根支持節(jié)點(diǎn)樹修復(fù)支持軟刪除依賴關(guān)于將樹中每個(gè)節(jié)點(diǎn)與其后代節(jié)點(diǎn) About 優(yōu)雅的樹形數(shù)據(jù)結(jié)構(gòu)管理包,基于Closure Table模式設(shè)計(jì). github 歡迎不吝Star Features 優(yōu)雅的樹形數(shù)據(jù)...

    aikin 評論0 收藏0

  • React Event 實(shí)現(xiàn)原理

    摘要：為組建的實(shí)例化對象為組件的唯一標(biāo)識為組建的實(shí)例化對象為事件名稱為我們寫的回調(diào)函數(shù)，也就是列子中的在每個(gè)中只實(shí)例化一次。 React 元素的事件處理和 DOM元素的很相似。但是有一點(diǎn)語法上的不同: React事件綁定屬性的命名采用駝峰式寫法，而不是小寫。 如果采用 JSX 的語法你需要傳入一個(gè)函數(shù)作為事件處理函數(shù)，而不是一個(gè)字符串(DOM元素的寫法) 并且 React 自己內(nèi)部實(shí)現(xiàn)了...

    xiguadada 評論0 收藏0

發(fā)表評論

0條評論

最新活動(dòng)
閱讀需要支付1元查看
<