[LintCode/LeetCode] Lowest Common Ancestor of BST/

dinfer 發布于2019-08-14 15:33 / 1808人閱讀

摘要：遞歸左右子樹，若左右子樹都有解，那么返回根節點若僅左子樹有解，返回左子樹若僅右子樹有解，返回右子樹若都無解，返回。對于而言，更為簡單公共祖先一定是大于等于其中一個結點，小于等于另一個結點。

Problem

Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.

The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.

Example

For the following binary tree:

LCA(3, 5) = 4

LCA(5, 6) = 7

LCA(6, 7) = 7

Note

遞歸左右子樹，若左右子樹都有解，那么返回根節點；若僅左子樹有解，返回左子樹；若僅右子樹有解，返回右子樹；若都無解，返回null。

對于BST而言，更為簡單：公共祖先一定是大于等于其中一個結點，小于等于另一個結點。那么若兩個結點都小于當前的root結點，完全可以繼續去比較第一個比root小的結點：root.left；若兩個結點都大于當前的root結點，就去比較第一個比root大的結點：root.right；否則，一定是滿足一個結點小于等于root，另一個結點大于等于root的情況了，返回root即可。

For the binary search tree, the root.val must be smaller than its right children but larger than its left children. Therefore, there are three basic possible relationships among root, p and q.

p.val >= root.val && q.val <= root.val;
p.val > root.val && q.val > root.val;
p.val < root.val && q.val < root.val;

Here we ignored the situation if we switch p and q, that"s equivalent situation to the first one, of which the result is root. So we just need to dig into the 2nd and 3rd.
For the 2nd situation, replace root with root.right cause the common ancestor must be larger than root, then we can just use recursion to get the answer.
Same for the 3rd.

Solution

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode A, TreeNode B) {
        if (root == null || root == A || root == B) return root;
        TreeNode left = lowestCommonAncestor(root.left, A, B);
        TreeNode right = lowestCommonAncestor(root.right, A, B);
        if (left != null && right != null) return root;
        if (left != null && right == null) return left;
        if (left == null && right != null) return right;
        return null;
    }
}

For BST：

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

云服務器 GPU云服務器 Ancestor Lowest Common BST

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

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

[Leetcode] Lowest Common Ancestor of a Binary Tree

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

Dr_Noooo 2019-08-14 12:25 評論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
FE-ES 前端數據結構與算法leedcode訓練合集40題

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

dabai 2019-08-23 16:14 評論0 收藏0
[LintCode/LeetCode] Convert Sorted List to Balance

摘要：當鏈表為空時，中出現大于，返回。然后計算中點，以為界分別遞歸構建左右子樹。順序是，左子樹根結點右子樹。由于根節點是直接取構建，當前的已經被取用。所以在下一次遞歸構建右子樹之前，要讓指向。最后將和左右子樹相連，返回。 Problem Given a singly linked list where elements are sorted in ascending order, conve...

Michael_Ding 2019-08-14 15:32 評論0 收藏0