国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

leetcode235-236 lowest common ancestor

chadLi / 2080人閱讀

摘要：如果左右子樹返回的最低共同父節(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 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.

現(xiàn)在有一棵搜索二叉樹，這個二叉樹的特點(diǎn)是左子樹的節(jié)點(diǎn)一定小于根節(jié)點(diǎn)，而右子樹的節(jié)點(diǎn)一定大于根節(jié)點(diǎn)。現(xiàn)在提供這棵樹的根節(jié)點(diǎn)，并且輸入兩個節(jié)點(diǎn)，問這兩個節(jié)點(diǎn)的最低共同父節(jié)點(diǎn)是誰？
最低共同父節(jié)點(diǎn)是指兩個節(jié)點(diǎn)在沿父節(jié)點(diǎn)向上爬升時遇到的第一個共同父節(jié)點(diǎn)，同時它也允許父節(jié)點(diǎn)就是其本身，比如在上圖中2和4的最低共同父節(jié)點(diǎn)就是2

思路和代碼

這里我們因為可以根據(jù)數(shù)值來判斷，需要尋找最低共同父節(jié)點(diǎn)的兩個節(jié)點(diǎn)跟當(dāng)前的根節(jié)點(diǎn)的大小比較，如果兩個值都比根節(jié)點(diǎn)小，則最小父節(jié)點(diǎn)一定在左子樹，二者都比它大，就在右子樹。否則當(dāng)前的根節(jié)點(diǎn)就是他們的最低共同父節(jié)點(diǎn)。

代碼如下：這里采用遞歸的方式來尋找

    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題 將搜索樹改變?yōu)橐话愕亩鏄?/b>

236題相對于235題而言，就是將題目中的搜索樹條件改變成了一般的二叉樹。這時我們無法通過和根節(jié)點(diǎn)比較數(shù)值大小來判斷最低共同父節(jié)點(diǎn)究竟是在左子樹還是右子樹還是就是當(dāng)前的根節(jié)點(diǎn)。

這時我們先試著用窮舉法來找到所有可能的情況，現(xiàn)在已知根節(jié)點(diǎn)root和兩個需要查找父節(jié)點(diǎn)的節(jié)點(diǎn)p,q

p, q分別位于root的左子樹和右子樹： root為最低共同父節(jié)點(diǎn)

p, q均位于root的左子樹: 繼續(xù)在root.left尋找最低共同父節(jié)點(diǎn)

p, q均為與root的右子樹: 繼續(xù)在root.right尋找最低共同父節(jié)點(diǎn)

root==p：最低共同父節(jié)點(diǎn)為p或p的某個父節(jié)點(diǎn)

root==q：最低共同父節(jié)點(diǎn)為q或q的某個父節(jié)點(diǎn)

我們再進(jìn)行匯總，如果我們在向下遍歷左子樹和右子樹的過程中，一旦遇到p或q，則返回p或q，因為繼續(xù)往下遍歷的值都不會是p和q的共同父節(jié)點(diǎn)。如果左右子樹返回的最低共同父節(jié)點(diǎn)值都不是空，說明p和q分別位于root的左右子樹，那么root就是最低共同父節(jié)點(diǎn)。如果兩個都為空，說明當(dāng)前根節(jié)點(diǎn)不包含p和q。如果其中一棵子樹返回的值不為空，那么就說明p和q都位于那棵子樹上，且返回的值就是遍歷過程中最先遇到的p或者q，也就是最低共同父節(jié)點(diǎn)。

代碼如下：

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


想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~

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

轉(zhuǎn)載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/68211.html

相關(guān)文章

  • [Leetcode] Lowest Common Ancestor of a Binary Tree

    摘要：如果子樹中有目標(biāo)節(jié)點(diǎn)，標(biāo)記為那個目標(biāo)節(jié)點(diǎn)，如果沒有，標(biāo)記為。顯然，如果左子樹右子樹都有標(biāo)記，說明就已經(jīng)找到最小公共祖先了。如果在根節(jié)點(diǎn)為的左右子樹中找的公共祖先，則必定是本身。只有一個節(jié)點(diǎn)正好左子樹有，右子樹也有的時候，才是最小公共祖先。 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)若僅左子樹有解，返回左子樹若僅右子樹有解，返回右子樹若都無解，返回。對于而言，更為簡單公共祖先一定是大于等于其中一個結(jié)點(diǎn)，小于等于另一個結(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

  • LCA---Lowest common ancestor

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

    cooxer 評論0 收藏0

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

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

    tain335 評論0 收藏0

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

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

    dabai 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<