[Leetcode] Lowest Common Ancestor of a Binary Tree

Dr_Noooo 發布于2019-08-14 12:25 / 2535人閱讀

摘要：如果子樹中有目標節點，標記為那個目標節點，如果沒有，標記為。顯然，如果左子樹右子樹都有標記，說明就已經找到最小公共祖先了。如果在根節點為的左右子樹中找的公共祖先，則必定是本身。只有一個節點正好左子樹有，右子樹也有的時候，才是最小公共祖先。

Lowest Common Ancestor of a Binary Search Tree 最新更新請見：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.

二分法 復雜度

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

思路

對于二叉搜索樹，公共祖先的值一定大于等于較小的節點，小于等于較大的節點。換言之，在遍歷樹的時候，如果當前結點大于兩個節點，則結果在當前結點的左子樹里，如果當前結點小于兩個節點，則結果在當前節點的右子樹里。

代碼

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 最新更新請見：https://yanjia.me/zh/2019/02/...

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

        _______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.

深度優先標記 復雜度

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

思路

我們可以用深度優先搜索，從葉子節點向上，標記子樹中出現目標節點的情況。如果子樹中有目標節點，標記為那個目標節點，如果沒有，標記為null。顯然，如果左子樹、右子樹都有標記，說明就已經找到最小公共祖先了。如果在根節點為p的左右子樹中找p、q的公共祖先，則必定是p本身。

換個角度，可以這么想：如果一個節點左子樹有兩個目標節點中的一個，右子樹沒有，那這個節點肯定不是最小公共祖先。如果一個節點右子樹有兩個目標節點中的一個，左子樹沒有，那這個節點肯定也不是最小公共祖先。只有一個節點正好左子樹有，右子樹也有的時候，才是最小公共祖先。

代碼

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //發現目標節點則通過返回值標記該子樹發現了某個目標結點
        if(root == null || root == p || root == q) return root;
        //查看左子樹中是否有目標結點，沒有為null
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        //查看右子樹是否有目標節點，沒有為null
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        //都不為空，說明做右子樹都有目標結點，則公共祖先就是本身
        if(left!=null&&right!=null) return root;
        //如果發現了目標節點，則繼續向上標記為該目標節點
        return left == null ? right : left;
    }
}

云服務器 GPU云服務器 binary-tree binary-search-tree Ancestor Lowest

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64470.html

[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
LCA---Lowest common ancestor

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

cooxer 2019-08-14 17:08 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

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

tain335 2019-08-26 10:28 評論0 收藏0
FE-ES 前端數據結構與算法leedcode訓練合集40題

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

dabai 2019-08-23 16:14 評論0 收藏0