[leetcode]Binary Tree Inorder Traversal

二叉树的中序遍历非递归版本，采用的是wiki百科上的办法。果然简洁，而且和先序有异曲同工之妙，先序只用push右节点，中序只用push中节点。除此之外还有个更改TreeNode加一个visited的bool值的办法就不表了。http://discuss.leetcode.com/questions/23/binary-tree-inorder-traversal 这个链接里面有个长长的讨论。后序遍历据说比较难，就先不学了，哪个面试官会这么变态出后序遍历么！！无堆栈版本的遍历也先不学了，有空多写先序和中序，要记熟了。

写的时候仍然要看图，不要光背，思路是：
1.当前节点一直是要处理的节点；
2.不停向左子树方向走，并push本节点；
3.走不下去了（null），就从栈中取刚才那个节点，打印，并变当前节点为右节点。

public class Solution {
    public ArrayList<Integer> inorderTraversal(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) {
                stack.push(n);
                n = n.left;
            }
            else {
                n = stack.pop();
                ans.add(n.val);
                n = n.right;
            }
        }
        return ans;
    }
}