[Leetcode - Tree] Binary Search Tree Iterator

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

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

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.解題思路

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

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