LeetCode 173 (binary-search-tree

空间复杂度：O(n)

package com.chen.li.JDK_RBT.bstIterator;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

class BSTIterator {
    private List<TreeNode> list = new ArrayList<TreeNode>();
    private Iterator<TreeNode> it;
    
    public BSTIterator(TreeNode root) {
        if(root != null) 
            initList(root);
        it = list.iterator();
    }
    
    private void initList(TreeNode node) {
        if(node == null)
            return;
        
        if(node.left != null) {
            initList(node.left);
        }
        
        list.add(node);
        
        if(node.right != null) {
            initList(node.right);
        }
            
    }

    /** @return the next smallest number */
    public int next() {
        return it.next().val;
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return it.hasNext();
    }
}

空间复杂度 O( log(n) )

package com.chen.li.JDK_RBT.bstIterator;

import java.util.Stack;

public class BSTIterator2 {
    Stack<TreeNode> stack = new Stack<>();
    
    public BSTIterator2(TreeNode root) {
        stackLeftNodes(root);
    }
    
    private void stackLeftNodes(TreeNode node) {
        while(node != null) {
            stack.push(node);
            node = node.left;
        }
        
    }
    
    /** @return the next smallest number */
    public int next() {
        TreeNode node = stack.pop();
        stackLeftNodes(node.right);
        
        return node.val;
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }
}