前序遍历非递归

1、申请一个栈stack，然后将头节点压入stack中。
2、从stack中弹出栈顶节点，打印，再将其右孩子节点（不为空的话）先压入stack中，最后将其左孩子节点（不为空的话）压入stack中。
3、不断重复步骤2，直到stack为空，全部过程结束。

/**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 import java.util.*;
11 class Solution {
12     public List<Integer> preorderTraversal(TreeNode root) {
13         List<Integer> list=new ArrayList<Integer>();
14         Stack<TreeNode> stack=new Stack<TreeNode>();
15         if (root!=null) {
16             stack.push(root);
17             while(!stack.empty()) {
18                 TreeNode tr=stack.pop();
19                 list.add(tr.val);
20                 if(tr.right!=null) {
21                     stack.push(tr.right);
22                 }
23                 if(tr.left!=null) {
24                      stack.push(tr.left);
25                 }
26             }
27         }   
28         return list;
29     }
30 }

中序遍历非递归

1、申请一个栈stack，初始时令cur=head

2、先把cur压入栈中，依次把左边界压入栈中，即不停的令cur=cur.left，重复步骤2

3、不断重复2，直到为null，从stack中弹出一个节点，记为node，打印node的值，并令cur=node.right,重复步骤2

4、当stack为空且cur为空时，整个过程停止。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode head) {
        List<Integer> list=new ArrayList<Integer>();
        Stack<TreeNode> stack=new Stack<TreeNode>();
        if (head!=null) {
            while(head!=null||!stack.empty()) {
                while(head!=null) {
                    stack.push(head);
                    head=head.left;
                }
                head=stack.pop();
                list.add(head);
                head=head.right;
            }
        }
        return list;
    }
}

后序遍历非递归

1、申请一个栈s1，然后将头节点压入栈s1中。

2、从s1中弹出的节点记为cur，然后依次将cur的左孩子节点和右孩子节点压入s1中。

3、在整个过程中，每一个从s1中弹出的节点都放进s2中。

4、不断重复步骤2和步骤3，直到s1为空，过程停止。

5、从s2中依次弹出节点并打印，打印的顺序就是后序遍历的顺序。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode head) {
        //原理其实和前序遍历一样，只是多用一个栈前序遍历的结果，然后把这个栈弹出清空其实就是后续遍历
        List<Integer> list=new ArrayList<Integer>();
        Stack<TreeNode> stack1=new Stack<TreeNode>();
        Stack<TreeNode> stack2=new Stack<TreeNode>();
        if (head!=null) {
            stack1.push(head);
            while(!stack1.empty()) {
                head=stack1.pop();
                stack2.push(head);
                if (head.left!=null) {
                    stack1.push(head.left);
                }
                if (head.right!=null) {
                    stack1.push(head.right);
                }
            }
            while(!stack2.empty()) {
                list.add(stack2.pop().val);
            }
        }
        return list;
    }
}