成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專(zhuān)欄INFORMATION COLUMN

[Leetcode] Lowest Common Ancestor of a Binary Tree

Dr_Noooo / 2587人閱讀

摘要：如果子樹(shù)中有目標(biāo)節(jié)點(diǎn)，標(biāo)記為那個(gè)目標(biāo)節(jié)點(diǎn)，如果沒(méi)有，標(biāo)記為。顯然，如果左子樹(shù)右子樹(shù)都有標(biāo)記，說(shuō)明就已經(jīng)找到最小公共祖先了。如果在根節(jié)點(diǎn)為的左右子樹(shù)中找的公共祖先，則必定是本身。只有一個(gè)節(jié)點(diǎn)正好左子樹(shù)有，右子樹(shù)也有的時(shí)候，才是最小公共祖先。

Lowest Common Ancestor of a Binary Search Tree 最新更新請(qǐng)見(jiàn)：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.
二分法 復(fù)雜度

時(shí)間 O(h) 空間 O(h) 遞歸?？臻g

思路

對(duì)于二叉搜索樹(shù)，公共祖先的值一定大于等于較小的節(jié)點(diǎn)，小于等于較大的節(jié)點(diǎn)。換言之，在遍歷樹(shù)的時(shí)候，如果當(dāng)前結(jié)點(diǎn)大于兩個(gè)節(jié)點(diǎn)，則結(jié)果在當(dāng)前結(jié)點(diǎn)的左子樹(shù)里，如果當(dāng)前結(jié)點(diǎn)小于兩個(gè)節(jié)點(diǎn)，則結(jié)果在當(dāng)前節(jié)點(diǎn)的右子樹(shù)里。

代碼 
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 最新更新請(qǐng)見(jiàn)：https://yanjia.me/zh/2019/02/... 
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.


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


        _______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.
深度優(yōu)先標(biāo)記 復(fù)雜度

時(shí)間 O(h) 空間 O(h) 遞歸棧空間

思路

我們可以用深度優(yōu)先搜索，從葉子節(jié)點(diǎn)向上，標(biāo)記子樹(shù)中出現(xiàn)目標(biāo)節(jié)點(diǎn)的情況。如果子樹(shù)中有目標(biāo)節(jié)點(diǎn)，標(biāo)記為那個(gè)目標(biāo)節(jié)點(diǎn)，如果沒(méi)有，標(biāo)記為null。顯然，如果左子樹(shù)、右子樹(shù)都有標(biāo)記，說(shuō)明就已經(jīng)找到最小公共祖先了。如果在根節(jié)點(diǎn)為p的左右子樹(shù)中找p、q的公共祖先，則必定是p本身。

換個(gè)角度，可以這么想：如果一個(gè)節(jié)點(diǎn)左子樹(shù)有兩個(gè)目標(biāo)節(jié)點(diǎn)中的一個(gè)，右子樹(shù)沒(méi)有，那這個(gè)節(jié)點(diǎn)肯定不是最小公共祖先。如果一個(gè)節(jié)點(diǎn)右子樹(shù)有兩個(gè)目標(biāo)節(jié)點(diǎn)中的一個(gè)，左子樹(shù)沒(méi)有，那這個(gè)節(jié)點(diǎn)肯定也不是最小公共祖先。只有一個(gè)節(jié)點(diǎn)正好左子樹(shù)有，右子樹(shù)也有的時(shí)候，才是最小公共祖先。

代碼 
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)則通過(guò)返回值標(biāo)記該子樹(shù)發(fā)現(xiàn)了某個(gè)目標(biāo)結(jié)點(diǎn)
        if(root == null || root == p || root == q) return root;
        //查看左子樹(shù)中是否有目標(biāo)結(jié)點(diǎn)，沒(méi)有為null
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        //查看右子樹(shù)是否有目標(biāo)節(jié)點(diǎn)，沒(méi)有為null
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        //都不為空，說(shuō)明做右子樹(shù)都有目標(biāo)結(jié)點(diǎn)，則公共祖先就是本身
        if(left!=null&&right!=null) return root;
        //如果發(fā)現(xiàn)了目標(biāo)節(jié)點(diǎn)，則繼續(xù)向上標(biāo)記為該目標(biāo)節(jié)點(diǎn)
        return left == null ? right : left;
    }
}

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/64470.html

相關(guān)文章

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

    摘要：遞歸左右子樹(shù)，若左右子樹(shù)都有解，那么返回根節(jié)點(diǎn)若僅左子樹(shù)有解，返回左子樹(shù)若僅右子樹(shù)有解，返回右子樹(shù)若都無(wú)解，返回。對(duì)于而言，更為簡(jiǎ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 評(píng)論0 收藏0

  • leetcode235-236 lowest common ancestor

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

  • LCA---Lowest common ancestor

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

    cooxer 評(píng)論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

    摘要：月下半旬攻略道題，目前已攻略題。目前簡(jiǎn)單難度攻略已經(jīng)到題，所以后面會(huì)調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚(yú)有什么區(qū)別...

    tain335 評(píng)論0 收藏0

  • FE-ES 前端數(shù)據(jù)結(jié)構(gòu)與算法leedcode訓(xùn)練合集40題

    摘要：無(wú)關(guān)知識(shí)點(diǎn)精通一個(gè)領(lǐng)域切碎知識(shí)點(diǎn)刻意練習(xí)反饋切題四件套審題所有解法比較時(shí)間空間復(fù)雜度加強(qiáng)編碼測(cè)試用例數(shù)組，鏈表數(shù)組查詢(xún)插入刪除鏈表查詢(xún)插入刪除翻轉(zhuǎn)鏈表兩兩翻轉(zhuǎn)鏈表判斷鏈表是否有環(huán)棧，隊(duì)列判斷合法括號(hào)棧模擬隊(duì)列隊(duì)列模擬棧找第大的元素 showImg(https://segmentfault.com/img/bVbqeRl?w=1600&h=1126); 無(wú)關(guān)知識(shí)點(diǎn) 1.精通一個(gè)領(lǐng)域： ...

    dabai 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

Dr_Noooo

男|高級(jí)講師

TA的文章

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