二叉树先序遍历

关于二叉树的遍历讲得最好的还是wiki：http://en.wikipedia.org/wiki/Pre-order_traversal

关于非递归版本，主要是在二叉树超级不平衡的情况下，有可能栈溢出。以下是我写得先序遍历非递归版本，应该是对的吧，没实际运行过，其实也不好写... 基本思路是用TreeNode * n去遍历，先左子树往下，完了pop出一个父节点，把自己变成右子树继续。所以Stack里存的其实是父节点的信息。以下是参考wiki百科的版本，栈用的很少，只推右子树。

  public class Solution {
	    public ArrayList<Integer> preorderTraversal(TreeNode root) {
	        ArrayList<Integer> ans = new ArrayList<Integer>();
	        Stack<TreeNode> stack = new Stack<TreeNode>();
	        TreeNode n = root;
	        while (n!= null || !stack.empty()) {            
	            if (n != null) {
	                ans.add(n.val);
	                if (n.right != null) {
	                	stack.push(n.right);
	                }
	                n = n.left;
	            }
	            else {
	                n = stack.pop();
	            }
	        }
	        return ans;
	    }
	}

其实还有一个更简单的版本，直接先把root.right推到栈里，然后root.left。但不知道为什么好像没有上面那个版本流行。大概如下，没有实际运行过。参考：http://blog.sina.com.cn/s/blog_a3d31db901016cgi.html

public class Solution {
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
    	ArrayList<Integer> ans = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while (!stack.empty()) {
        	TreeNode n = stack.pop();
        	if (n != null) {
        		ans.add(n.val);
        		stack.push(n.right);
        		stack.push(n.left);
        	}
        }
        return ans;
    }
}