Preorder, Inorder, and Postorder非递归总结

Preorder, Inorder, and Postorder Iteratively Summarization[1]

1.Pre Order Traverse

 1 public List<Integer> preorderTraversal(TreeNode root) {
 2     List<Integer> result = new ArrayList<>();
 3     Deque<TreeNode> stack = new ArrayDeque<>();
 4     TreeNode p = root;
 5     while(!stack.isEmpty() || p != null) {
 6         if(p != null) {
 7             stack.push(p);
 8             result.add(p.val);  // Add before going to children
 9             p = p.left;
10         } else {
11             TreeNode node = stack.pop();
12             p = node.right;   
13         }
14     }
15     return result;
16 }

2.In Order Traverse

 1 public List<Integer> inorderTraversal(TreeNode root) {
 2     List<Integer> result = new ArrayList<>();
 3     Deque<TreeNode> stack = new ArrayDeque<>();
 4     TreeNode p = root;
 5     while(!stack.isEmpty() || p != null) {
 6         if(p != null) {
 7             stack.push(p);
 8             p = p.left;
 9         } else {
10             TreeNode node = stack.pop();
11             result.add(node.val);  // Add after all left children
12             p = node.right;   
13         }
14     }
15     return result;
16 }

3.Post Order Traverse

 1 public List<Integer> postorderTraversal(TreeNode root) {
 2     LinkedList<Integer> result = new LinkedList<>();
 3     Deque<TreeNode> stack = new ArrayDeque<>();
 4     TreeNode p = root;
 5     while(!stack.isEmpty() || p != null) {
 6         if(p != null) {
 7             stack.push(p);
 8             result.addFirst(p.val);  // Reverse the process of preorder
 9             p = p.right;             // Reverse the process of preorder
10         } else {
11             TreeNode node = stack.pop();
12             p = node.left;           // Reverse the process of preorder
13         }
14     }
15     return result;
16 }