[Leetcode - Tree] Binary Search Tree Iterator

jsyzchen 發(fā)布于2019-08-16 10:26 / 887人閱讀

摘要：解題思路對于二叉搜索樹，我們很容易會想到使用棧和隊列來解決問題，本題是要求實現一個對二叉搜索樹的遍歷器，要求每次可以返回最小的節(jié)點值，我們使用棧。

Binary Search Tree Iterator
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

1.解題思路

對于二叉搜索樹，我們很容易會想到使用棧和隊列來解決問題，本題是要求實現一個對二叉搜索樹的遍歷器，要求每次可以返回最小的節(jié)點值，我們使用棧。
1）hasnext()，很容易實現，只要判斷棧是否為空；
2）BSTIterator構造函數，我們可以從根節(jié)點開始，陸續(xù)將左節(jié)點壓入棧中，這樣迭代器構造完后，棧頂元素就是最小的；
3）next()，每次pop出的棧頂元素，該元素肯定不會有左節(jié)點，但是我們需要判斷其是否有右節(jié)點，如果有，我們要將右節(jié)點壓入棧中，而且還要繼續(xù)將右節(jié)點下面的所有左節(jié)點壓入棧中，這樣才能保證棧頂元素就是最小的。

2.代碼

public class BSTIterator {
    Stack s=new Stack();
    public BSTIterator(TreeNode root) {
        if(root!=null){
            s.push(root);
            pushLeft(root);
        }
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !s.empty();
    }

    /** @return the next smallest number */
    public int next() {
        TreeNode node=s.pop();
        int value=node.val;
        TreeNode rnode=node.right;
        if(rnode!=null){
            s.push(rnode);
            pushLeft(rnode);
        }
        return value;
    }
    private void pushLeft(TreeNode root){
        TreeNode node=root.left;
        while(node!=null){
                s.push(node);
                node=node.left;
            }
    }
}

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

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

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

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

摘要：代碼先找到第一個節(jié)點，并把路徑入棧棧為空時不再有下一個棧頂是待返回元素如果該元素有右節(jié)點，把它的右節(jié)點及右節(jié)點的所有左邊節(jié)點都壓入棧中 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
[LintCode] Binary Search Tree Iterator

摘要：建立一個堆棧，先將最左邊的結點從大到小壓入棧，這樣的話，為了實現迭代即返回下一個的函數就要考慮右邊的結點。如此，實現函數。 Problem Design an iterator over a binary search tree with the following rules: Elements are visited in ascending order (i.e. an in-o...

silencezwm 2019-08-14 15:33 評論0 收藏0
leetcode98. Validate Binary Search Tree

摘要：題目要求檢驗二叉查找樹是否符合規(guī)則。二叉查找樹是指當前節(jié)點左子樹上的值均比其小，右子樹上的值均比起大。因此在這里我們采用棧的方式實現中序遍歷，通過研究中序遍歷是否遞增來判斷二叉查找樹是否符合規(guī)則。題目要求 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is...

codercao 2019-08-15 10:56 評論0 收藏0
leetcode98. Validate Binary Search Tree

摘要：題目要求檢驗二叉查找樹是否符合規(guī)則。二叉查找樹是指當前節(jié)點左子樹上的值均比其小，右子樹上的值均比起大。因此在這里我們采用棧的方式實現中序遍歷，通過研究中序遍歷是否遞增來判斷二叉查找樹是否符合規(guī)則。題目要求 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is...

AlphaWatch 2019-08-15 10:56 評論0 收藏0
leetcode98. Validate Binary Search Tree

摘要：題目要求判斷一個樹是否是二叉查找樹。二叉查找樹即滿足當前節(jié)點左子樹的值均小于當前節(jié)點的值，右子樹的值均大于當前節(jié)點的值。思路一可以看到，對二叉查找樹的中序遍歷結果應當是一個遞增的數組。這里我們用堆棧的方式實現中序遍歷。題目要求 given a binary tree, determine if it is a valid binary search tree (BST). Assu...

songze 2019-08-15 10:56 評論0 收藏0