二叉树遍历思想(二) : 中序遍历

　　二叉树的中序遍历递归定义 : 

　　1) 当前节点为空(null)直接返回

　　2) 对于非空节点

　　　　i)   中序遍历左子树

　　　　ii)  操作当前节点

　　　　iii) 中序遍历右子树

　　二叉树的非递归遍历方法 : 

　　　　使用栈来进行遍历。

　　　　策略简述 ： 

　　　　　　利用栈和循环,每次循环的输入变量node都必须为当前要遍历的树的根节点。也就是将循环当作递归函数使用。

　　　　　　例如当前输入node = root,那么只要使得 root 和 root.right 成对出现就能辨别哪个是root,哪个是root.right。首先第一步是把当前层的root.right压栈,再将root压栈。那么下次无论如何root.right都是在root后面出现。并且这里的root是留着左子树遍历结束后再进行遍历根节点,再遍历右子树。而循环的含义是将root整个树中序遍历,于是node = root不应该再次作为循环输入的参数。而应该在node = node.right,之前默默地将其处理掉。

　　　　　　那么如何实现上述例子呢?

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.push(root.right);
                stack.push(root);
                root = root.left;
            }else {
                res.add(stack.pop().val); // 根节点
                root = stack.pop(); // 右子树
            }
        }return res;
    }
}