Leetcode - Binary Tree Preorder || Postorder || Inorder Traversal

递归的方法就不赘述了，下面列三种的iterative方法：

 I: Preorder:
借助stack，每次先push右孩子再push左孩子，这样保证每次先处理左子树。

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

II:Postorder

public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
      //iteration
      ArrayList<Integer> res = new ArrayList<Integer>();
      if(root==null) return res;
      
      HashMap<TreeNode, Boolean> map = new HashMap<TreeNode, Boolean>();
      Stack<TreeNode> stack = new Stack<TreeNode>();
      stack.push(root);
      
      while(!stack.isEmpty()){
          TreeNode temp = stack.peek();
          if(temp.left!=null && !map.containsKey(temp.left))
            stack.push(temp.left);
          else if(temp.right!=null && !map.containsKey(temp.right))
            stack.push(temp.right);
          else{
              res.add(stack.pop().val);
              map.put(temp, true);
          }
      }
      return res;   
    }
}

III: Inorder

public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if(root==null) return res;
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        HashSet<TreeNode> set = new HashSet<TreeNode>();
        set.add(root);
        while(!stack.isEmpty()){
            TreeNode cur = stack.peek();
            if(cur.left!=null && !set.contains(cur.left))
                stack.push(cur.left);
            else{
                res.add(stack.pop().val);
                set.add(cur);
                if(cur.right!=null)
                    stack.push(cur.right);
            }
        }
        return res;
    }
}