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

marek 發布于2019-08-14 12:36 / 1259人閱讀

摘要：所以我們要找的上面，實際上是從目標節點向根節點回溯時，第一個比目標節點大的節點。

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.

路徑入棧法 復雜度

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

思路

題目給定根節點和目標節點。目標節點如果有右節點的情況比較好處理，我們只要返回它的右節點的最左邊的節點就行了（右節點自己沒有左節點時則是右節點本身）。如果目標節點沒有右節點，說明比目標節點稍大的節點應該在上面，因為我們知道目標節點的左節點肯定是比目標節點要小的。

那怎么知道目標節點的上面是什么呢？這時就需要從根節點搜索到目標節點了。這里要注意的是，目標節點的父親不一定比目標節點大，因為有可能目標節點的是其父親的右孩子。所以我們要找的上面，實際上是從目標節點向根節點回溯時，第一個比目標節點大的節點。最差的情況下，如果回溯到根節點還是比目標節點要小的話，說明目標節點就是整個數最大的數了，這時候返回空。

那怎么實現目標節點向根節點回溯，這里用一個棧就行了，在我們尋找目標節點時，把路徑上的節點都壓入棧中。

代碼

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

云服務器 GPU云服務器樹中序 Successor Inorder 用js制作一個搜索框

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

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

【LeetCode 二叉樹專項】二叉搜索樹中的中序后繼（285）

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

ccj659 2021-11-24 09:39 評論0 收藏0
【LeetCode 二叉樹專項】把二叉搜索樹轉換為累加樹（538）

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

xcold 2021-11-18 10:02 評論0 收藏0
LeetCode 272 Closest Binary Tree Traversal II 解題思路

摘要：原題網址題意在二叉搜索樹當中找到離最近的個數。解題思路由于二叉搜索數的中序遍歷是有序的，比如例子中的樹，中序遍歷為。原題網址：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 2019-08-16 13:26 評論0 收藏0
[Leetcode] Binary Search Tree Iterator 二叉搜素樹迭代器

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

shixinzhang 2019-08-14 12:36 評論0 收藏0
我理解的數據結構（五）—— 二分搜索樹（Binary Search Tree）

摘要：我理解的數據結構五二分搜索樹一二叉樹和鏈表一樣，動態數據結構具有唯一根節點每個節點最多有兩個子節點每個節點最多有一個父節點具有天然的遞歸結構每個節點的左子樹也是二叉樹每個節點的右子樹也是二叉樹一個節點或者空也是二叉樹二二分搜索樹是二叉樹每個我理解的數據結構（五）—— 二分搜索樹（Binary Search Tree）一、二叉樹和鏈表一樣，動態數據結構具有唯一根節點每個節點最...

xeblog 2019-08-19 11:13 評論0 收藏0