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

資訊專欄INFORMATION COLUMN

[LintCode/LeetCode] Lowest Common Ancestor of BST/

dinfer / 1866人閱讀

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

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:

  4
 / 
3   7
   / 
  5   6

LCA(3, 5) = 4

LCA(5, 6) = 7

LCA(6, 7) = 7

Note

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

對于BST而言，更為簡單：公共祖先一定是大于等于其中一個結(jié)點，小于等于另一個結(jié)點。那么若兩個結(jié)點都小于當(dāng)前的root結(jié)點，完全可以繼續(xù)去比較第一個比root小的結(jié)點：root.left；若兩個結(jié)點都大于當(dāng)前的root結(jié)點，就去比較第一個比root大的結(jié)點：root.right；否則，一定是滿足一個結(jié)點小于等于root，另一個結(jié)點大于等于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;
    }
}

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

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

相關(guān)文章

  • [Leetcode] Lowest Common Ancestor of a Binary Tree

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

    Dr_Noooo 評論0 收藏0

  • leetcode235-236 lowest common ancestor

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

  • LCA---Lowest common ancestor

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

    cooxer 評論0 收藏0

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

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

    dabai 評論0 收藏0

  • [LintCode/LeetCode] Convert Sorted List to Balance

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

    Michael_Ding 評論0 收藏0

發(fā)表評論

0條評論

閱讀需要支付1元查看
<