leetCode-173:Binary Search Tree Iterator

问题描述

给定一个二叉搜索树，要求按照中序输出的方式构造二叉搜索树的迭代器。其中 next 和 hasNext 函数的时间复杂度为 O(1)，空间复杂度为 O(h), h 指树的高度。题目链接：**点我**

问题解法

用一个栈来存储中序遍历过程中的左节点，调用 next 函数时，直接从栈中取出元素，同时判断该节点是否有右节点，如果有，则将该节点右子树的左节点遍历放入栈中。调用 hasNext 函数时，直接判断栈是否有空，为空则返回 false，否则返回 true。代码如下

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class BSTIterator
{
    private Stack<TreeNode> stack = new Stack<>();

    public BSTIterator(TreeNode root)
    {
        stack = new Stack<>();
        addStack(root);
    }

    public int next()
    {
        TreeNode current = stack.pop();
        addStack(current.right);
        return current.val;
    }

    public boolean hasNext()
    {
        return !stack.isEmpty();
    }

    private void addStack(TreeNode root)
    {
        TreeNode current = root;
        while (current != null)
        {
            stack.push(current);
            current = current.left;
        }
    }
}