LeetCode 173. Binary Search Tree Iterator

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2016/10/24/LeetCode-173-Binary-Search-Tree-Iterator/
访问原文「LeetCode 173. Binary Search Tree Iterator」

昨天夜里

昨天夜里，家里很冷，心想着该睡了。突然灵机一动，想到自己很久没有刷题了，要不然带一道题入睡吧。心想着也不要太复杂的题，好久没刷了，太复杂估计一时半会儿想不出来。那就来道Easy的吧，看了一道，太简单了吧。索性换一道Medium难度的吧，于是随机的选了这一道。这一道的要求是时间复杂度O(1)、空间复杂度O(h)，所以还得好好想想。

我还没有想出来怎么做就睡着了，当然（为什么当然？！），在入睡前我的思绪也没有全在这道题上，可能想着想着就飞了。今儿早一醒，也不想起，就想到了这道题，也是突然灵机一动想出来怎么做，然后迅速的把它搞定了。

流水结束。

原题要求

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.

我的解法

public class BSTIterator {
	Stack<TreeNode> stack = new Stack<TreeNode>();
	public BSTIterator(TreeNode root) {
		TreeNode temp = root;
		while (null != temp) {
			stack.push(temp);
			temp = temp.left;
		}
	}
	/** @return whether we have a next smallest number */
	public boolean hasNext() {
		if (!stack.empty()) {
			return true;
		}
		return false;
	}
	/** @return the next smallest number */
	public int next() {
		TreeNode temp = stack.pop();
		if (null != temp.right) {
			TreeNode newTemp = temp.right;
			while (null != newTemp) {
				stack.push(newTemp);
				newTemp = newTemp.left;
			}
		}
		return temp.val;
	}
}

解法思路

解法的本质就是dfs，只不过将dfs的结果做缓存，在获取next()以及调用hasNext()的时候都是基于这个缓存。

首先是初始化，大家都知道二分搜索树是左子树的值小于右子树的值，所以最小的值一定在从根节点开始的最左子树，如果对于这个结论不太理解的话，建议还是自己画一个或者几个二分搜索树来分析一下。所以初始化就是将从根节点开始到最左子树的过程中的所有节点放入栈。为什么用栈呢，很明显我们这里是一个先入后出的应用，所以只能用栈。

然后是hasNext()函数，这个就简单了，栈里有东西代表true，没有就是false;

接着是next()函数，这个是最重要的。根据之前的分析，可以知道栈里pop出来的就是当前最小的。这个时候要知道，这个节点可能是有右子树的，我们知道右子树的值是大于左子树以及父节点的，但是右子树的所有值是小于父节点的父节点也就是爷爷节点，所以在pop之后，需要将以右子树的根节点为起始，将从该根节点到其最左节点之间（包含）的所有节点入栈。最后返回pop出来的那个值。

这个思路可能说起来比较的不好理解，那么就在纸上画画，这个便于理解。