成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] Inorder Successor in BST 二叉搜索樹中序下一個

marek / 1267人閱讀

摘要：所以我們要找的上面，實(shí)際上是從目標(biāo)節(jié)點(diǎn)向根節(jié)點(diǎn)回溯時，第一個比目標(biāo)節(jié)點(diǎn)大的節(jié)點(diǎn)。

Inorder Successor in BST 
Given a binary search tree and a node in it, find the in-order successor of that node in the BST.


Note: If the given node has no in-order successor in the tree, return null.
路徑入棧法 復(fù)雜度

時間 O(N) 空間 O(N)

思路

題目給定根節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)。目標(biāo)節(jié)點(diǎn)如果有右節(jié)點(diǎn)的情況比較好處理，我們只要返回它的右節(jié)點(diǎn)的最左邊的節(jié)點(diǎn)就行了（右節(jié)點(diǎn)自己沒有左節(jié)點(diǎn)時則是右節(jié)點(diǎn)本身）。如果目標(biāo)節(jié)點(diǎn)沒有右節(jié)點(diǎn)，說明比目標(biāo)節(jié)點(diǎn)稍大的節(jié)點(diǎn)應(yīng)該在上面，因?yàn)槲覀冎滥繕?biāo)節(jié)點(diǎn)的左節(jié)點(diǎn)肯定是比目標(biāo)節(jié)點(diǎn)要小的。

那怎么知道目標(biāo)節(jié)點(diǎn)的上面是什么呢？這時就需要從根節(jié)點(diǎn)搜索到目標(biāo)節(jié)點(diǎn)了。這里要注意的是，目標(biāo)節(jié)點(diǎn)的父親不一定比目標(biāo)節(jié)點(diǎn)大，因?yàn)橛锌赡苣繕?biāo)節(jié)點(diǎn)的是其父親的右孩子。所以我們要找的上面，實(shí)際上是從目標(biāo)節(jié)點(diǎn)向根節(jié)點(diǎn)回溯時，第一個比目標(biāo)節(jié)點(diǎn)大的節(jié)點(diǎn)。最差的情況下，如果回溯到根節(jié)點(diǎn)還是比目標(biāo)節(jié)點(diǎn)要小的話，說明目標(biāo)節(jié)點(diǎn)就是整個數(shù)最大的數(shù)了，這時候返回空。

那怎么實(shí)現(xiàn)目標(biāo)節(jié)點(diǎn)向根節(jié)點(diǎn)回溯，這里用一個棧就行了，在我們尋找目標(biāo)節(jié)點(diǎn)時，把路徑上的節(jié)點(diǎn)都壓入棧中。

代碼 
public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        Stack stk = new Stack();
        TreeNode curr = root;
        // 找到目標(biāo)節(jié)點(diǎn)并把路徑上的節(jié)點(diǎn)壓入棧
        while(curr != p){
            stk.push(curr);
            if(curr.val > p.val){
                curr = curr.left;
            } else {
                curr = curr.right;
            }
        }
        // 如果目標(biāo)節(jié)點(diǎn)有右節(jié)點(diǎn)，則找到其右節(jié)點(diǎn)的最左邊的節(jié)點(diǎn)，就是下一個數(shù)
        if(curr.right != null){
            curr = curr.right;
            while(curr.left != null){
                curr = curr.left;
            }
            return curr;
        } else {
        // 如果沒有右節(jié)點(diǎn)，pop棧找到第一個比目標(biāo)節(jié)點(diǎn)大的節(jié)點(diǎn)
            while(!stk.isEmpty() && stk.peek().val < curr.val){
                stk.pop();
            }
            // 如果棧都pop空了還沒有比目標(biāo)節(jié)點(diǎn)大的，說明沒有更大的了
            return stk.isEmpty() ? null : stk.pop();
        }
    }
}

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64584.html

相關(guān)文章

  • 【LeetCode 二叉樹專項(xiàng)】二叉搜索樹中的中序后繼（285）

    摘要：解法二迭代中序遍歷分析作者二叉搜索樹的中序后繼是中序遍歷中當(dāng)前節(jié)點(diǎn)之后最小的節(jié)點(diǎn)。 文章目錄 1. 題目1.1 示例1.2 說明1.3 限制 2....

    ccj659 評論0 收藏0

  • 【LeetCode 二叉樹專項(xiàng)】把二叉搜索樹轉(zhuǎn)換為累加樹（538）

    摘要：解法一中序遍歷分析由于給定了二叉搜索樹，因此首先考慮中序遍歷，使用示例，我們先來分別看一下二叉搜索樹和累加樹中序遍歷的結(jié)果二叉搜索樹二叉累加樹。這里還是使用示例，我們再來觀察一下二叉搜索樹和累加樹中序遍歷的結(jié)果二叉搜索樹二叉累加樹。 ...

    xcold 評論0 收藏0

  • LeetCode 272 Closest Binary Tree Traversal II 解題思路

    摘要：原題網(wǎng)址題意在二叉搜索樹當(dāng)中找到離最近的個數(shù)。解題思路由于二叉搜索數(shù)的中序遍歷是有序的，比如例子中的樹，中序遍歷為。 原題網(wǎng)址：https://leetcode.com/problems... Given a non-empty binary search tree and a target value, find?k?values in the BST that are closes...

    Youngdze 評論0 收藏0

  • [Leetcode] Binary Search Tree Iterator 二叉搜素樹迭代器

    摘要：代碼先找到第一個節(jié)點(diǎn)，并把路徑入棧棧為空時不再有下一個棧頂是待返回元素如果該元素有右節(jié)點(diǎn)，把它的右節(jié)點(diǎn)及右節(jié)點(diǎn)的所有左邊節(jié)點(diǎn)都壓入棧中 Binary Search Tree Iterator 最新更新：https://yanjia.me/zh/2019/02/... Implement an iterator over a binary search tree (BST). Your...

    shixinzhang 評論0 收藏0

  • 我理解的數(shù)據(jù)結(jié)構(gòu)（五）—— 二分搜索樹（Binary Search Tree）

    摘要：我理解的數(shù)據(jù)結(jié)構(gòu)五二分搜索樹一二叉樹和鏈表一樣，動態(tài)數(shù)據(jù)結(jié)構(gòu)具有唯一根節(jié)點(diǎn)每個節(jié)點(diǎn)最多有兩個子節(jié)點(diǎn)每個節(jié)點(diǎn)最多有一個父節(jié)點(diǎn)具有天然的遞歸結(jié)構(gòu)每個節(jié)點(diǎn)的左子樹也是二叉樹每個節(jié)點(diǎn)的右子樹也是二叉樹一個節(jié)點(diǎn)或者空也是二叉樹二二分搜索樹是二叉樹每個 我理解的數(shù)據(jù)結(jié)構(gòu)（五）—— 二分搜索樹（Binary Search Tree） 一、二叉樹 和鏈表一樣，動態(tài)數(shù)據(jù)結(jié)構(gòu) 具有唯一根節(jié)點(diǎn) 每個節(jié)點(diǎn)最...

    xeblog 評論0 收藏0

發(fā)表評論

0條評論

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