Tree Traversal

题目：
树的前序遍历recursive版，前序遍历iterative版，后序遍历iterative版，中序遍历iterative版。

解题思路：
iterative的话就是用stack来实现。

代码：

public class TreeTraversal {

    // three order iteration    
    public List<Integer> preorderTraversalIter(TreeNode root){
        List<Integer> rst = new ArrayList<Integer>();
        if(root == null){
            return rst;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            rst.add(node.val);
            if(node.right != null){
                stack.push(node.right);
            }
            if(node.left != null){
                stack.push(node.left);
            }
        }
        return rst;
    }

    public List<Integer> inTraversalIter(TreeNode root){
        List<Integer> rst = new ArrayList<Integer>();
        if(root == null){
            return rst;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode next = root;
        while(next != null || !stack.isEmpty()){
            while(next != null){
                stack.push(next);
                next = next.left;
            }
            next = stack.pop();
            rst.add(next.val);
            next = next.right;
        }
        return rst;
    }

    public List<Integer> postTraversalIter(TreeNode root){
        List<Integer> rst = new ArrayList<Integer>();
        if(root == null){

            return rst;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            rst.add(0, node.val);
            if(node.left != null){
                stack.push(node.left);
            }
            if(node.right != null){
                stack.push(node.right);
            }
        }
        return rst;
    }


////    // three order recursion//    public List<Integer> preorderTraversalRecur(TreeNode root){////    }////    public List<Integer> inTraversalRecur(TreeNode root){////    }////    public List<Integer> postTraversalRecur(TreeNode root){////    }
}