[LeetCode]Binary Tree Preorder Traversal

BST遍历的问题，很经典的问题。
前序后序中序，递归的解法非常的简单，因为递归可以很好地模拟第一次，第二次，第三次到达一个节点的情况，相对的，我们只需决定在第一次，第二次还是第三次访问这个节点的时候记录他的值。不过对于对于非递归解法，难点就在于我们要模拟第一次第二次第三次到达某个节点的情况。对于前序和中序来说相对简单，我们只需要维护一个stack即可，每次去左子树到无路可去的时候弹出后继节点。这个方法可以很好地模拟第一次，和第二次访问的情况。但对于后序，这个方法并不好使。

代码如下：

	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	public class Solution {
	public List<Integer> preorderTraversal(TreeNode root) {
	List<Integer> res = new ArrayList<Integer>();
	if (root == null)
	return res;
	TreeNode curr = root;
	Stack<TreeNode> path = new Stack<TreeNode>();
	while(!path.isEmpty() || curr != null) {
	while (curr != null) {
	path.push(curr);
	res.add(curr.val);
	curr = curr.left;
	}
	curr = path.pop();
	curr = curr.right;
	}
	return res;
	}
	}

view raw bst preorder.java hosted with ❤ by GitHub

注意前序和中序在这唯一的区别只在于，是第一次访问加入结果集还是第二次。
下面证明一下这个方法的正确性，我们要证明的是在我们每次无路可去的时候弹出的一定是当前节点的后继节点。
首先我们明确两个情况，对于有右子树的节点，他的后继节点一定是右子树的最小值。如果没有右子树，它的后继结点一定在从root到它的路径上。从这个节点c向上回溯，直到发现c在当前节点p的左子树里，那么p是c的后继节点，如果我们找不到p说明我们到的是最大的一个节点，也是最后一个节点。
对于第一种情况，因为我们每次找的都是子树的最左节点，所以肯定是可以保证的。对于第二种情况，当我们pop的时候，由于stack里存的是路径上的节点，在这个时候，后继节点之前的节点肯定已经被pop掉了。因为当前节点c既然是在那些节点的右子树，那么因为我们进入一个节点的右子树前一定会pop出这个节点（代码第23行），所以我们现在pop出的节点一定是后继节点。
当我们到最后一个节点的时候，没有右子树，curr == null，并且路径上的节点全部被pop掉了，因为当前节点是在路径上所有节点的右子树。循环结束。
所以可以证明这个算法是正确的。

Follow up: constant space的前序遍历。