leetcode235-236 lowest common ancestor

chadLi 發(fā)布于2019-08-15 13:37 / 2074人閱讀

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

思路和代碼

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

代碼如下：這里采用遞歸的方式來(lái)尋找

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

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

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

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

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

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

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

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

我們?cè)龠M(jìn)行匯總，如果我們?cè)谙蛳卤闅v左子樹(shù)和右子樹(shù)的過(guò)程中，一旦遇到p或q，則返回p或q，因?yàn)槔^續(xù)往下遍歷的值都不會(huì)是p和q的共同父節(jié)點(diǎn)。如果左右子樹(shù)返回的最低共同父節(jié)點(diǎn)值都不是空，說(shuō)明p和q分別位于root的左右子樹(shù)，那么root就是最低共同父節(jié)點(diǎn)。如果兩個(gè)都為空，說(shuō)明當(dāng)前根節(jié)點(diǎn)不包含p和q。如果其中一棵子樹(shù)返回的值不為空，那么就說(shuō)明p和q都位于那棵子樹(shù)上，且返回的值就是遍歷過(guò)程中最先遇到的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;
    }

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