平时都写递归的，非递归的都忘光光了，学习一下?
非递归实现二叉树先序、中序和后序遍历
用递归方式实现二叉树先序、中序和后序遍历很简单。
用递归方法解决的问题都能用非递归的方法实现。递归就是利用函数栈来保存信息，如果用自己申请的数据结构来代替函数栈，也可以实现相同的功能。
用非递归的方式实现二叉树的先序遍历（LeetCode144）：
1、申请一个栈stack，然后将头节点压入stack中。
2、从stack中弹出栈顶节点，打印，再将其右孩子节点（不为空的话）先压入stack中，最后将其左孩子节点（不为空的话）压入stack中。
3、不断重复步骤2，直到stack为空，全部过程结束。
1 /**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 }
用非递归的方式实现二叉树的中序遍历（LeetCode94）：
1、申请一个栈stack，初始时令cur=head
2、先把cur压入栈中，依次把左边界压入栈中，即不停的令cur=cur.left，重复步骤2
3、不断重复2，直到为null，从stack中弹出一个节点，记为node，打印node的值，并令cur=node.right,重复步骤2
4、当stack为空且cur为空时，整个过程停止。
1 /**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 class Solution {
11 public List<Integer> inorderTraversal(TreeNode head) {
12 List<Integer> list=new ArrayList<Integer>();
13 Stack<TreeNode> stack=new Stack<TreeNode>();
14 if (head!=null) {
15 while(head!=null||!stack.empty()) {
16 if(head!=null) {
17 stack.push(head);
18 head=head.left;
19 }else {
20 head=stack.pop();
21 list.add(head.val);
22 head=head.right;
23 }
24 }
25 }
26 return list;
27 }
28 }
用非递归的方式实现二叉树的后序遍历（LeetCode145）：
用非递归的方式实现后序遍历有点麻烦。
1、申请一个栈s1，然后将头节点压入栈s1中。
2、从s1中弹出的节点记为cur，然后依次将cur的左孩子节点和右孩子节点压入s1中。
3、在整个过程中，每一个从s1中弹出的节点都放进s2中。
4、不断重复步骤2和步骤3，直到s1为空，过程停止。
5、从s2中依次弹出节点并打印，打印的顺序就是后序遍历的顺序。
1 /**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 class Solution {
11 public List<Integer> postorderTraversal(TreeNode head) {
12 List<Integer> list=new ArrayList<Integer>();
13 Stack<TreeNode> stack1=new Stack<TreeNode>();
14 Stack<TreeNode> stack2=new Stack<TreeNode>();
15 if (head!=null) {
16 stack1.push(head);
17 while(!stack1.empty()) {
18 head=stack1.pop();
19 stack2.push(head);
20 if (head.left!=null) {
21 stack1.push(head.left);
22 }
23 if (head.right!=null) {
24 stack1.push(head.right);
25 }
26 }
27 while(!stack2.empty()) {
28 list.add(stack2.pop().val);
29 }
30 }
31 return list;
32 }
33 }