非递归前中后序遍历二叉树

1 前序遍历

前序遍历为：根、左、右，我们可以借助一个栈来完成遍历，大致思路如下：

• 第一次根节点进栈，然后每次栈顶元素出栈，打印根节点的值value;
• 根节点的右节点进栈；
• 根节点的左结点进栈；
  这里是右节点先进栈，然后才是左节点进栈，那么下次出栈的时候就是左节点先出栈，即先遍历根节点的左节点。

参考代码：

public void preOrder(TreeNode root){
    
	if(root == null)return;
	LinkedList<TreeNode> stack = new LinkedList<>();
	stack.addLast(root);
	while(!stack.isEmpty()){
    
		root = stack.removeLast();
		System.out.print(root.val + " ");
		if(root.right != null)stack.addLast(root.right);//右子结点先进栈
		if(root.left != null)stack.addLast(root.left);//左子结点后进栈
    }
    
}

---

2 中序遍历

前序遍历为：左、根、右，我们也可以借助一个栈来完成遍历，大致思路如下：

• 根结点进栈，左孩子不为空，左孩子进栈，左孩子的左孩子不为空，左孩子的左孩子进栈 …，直到遇到null；
• 遇到null，栈中出栈一个元素，打印value，判断出栈元素有没有右孩子，若有，右孩子进栈，重复第一步的操作，即将它的左孩子进栈。

参考代码：

public void inOrder(TreeNode root){
    
   if(root == null)return;
   LinkedList<TreeNode> stack = new LinkedList<>();
   while(!stack.isEmpty() || root != null){
    
     if(root != null){
    
       stack.addLast(root);
       root = root.left;  //每次将左孩子进栈
     }
	 else{
    
        root = stack.removeLast();
        System.out.print(root.val + " ");
        root = root.right;//下次循环，右孩子进栈
     }
   }
}

---

3 后序遍历

后序遍历顺序为：左、右、根。这里要借助2个栈来完成。大致思路如下：

• 第一次将根节点入栈1，后面每次栈顶元素出栈并进入栈2；
• 根节点的左孩子不为空，左孩子进栈1；
• 根节点的右孩子不为空，右孩子进栈1；
• 重复上述操作（此时根节点不用进栈）

这样的话，栈2元素的顺序从栈底到栈顶为：根、右、左。那么栈2进行一次出栈后，出栈顺序为左、右、根。

public void postOrder(TreeNode root){
    
  if(root== null)return;
  LinkedList<TreeNode> stack1 = new LinkedList<>();
  LinkedList<TreeNode> stack2 = new LinkedList<>();
  stack1.addLast(root);
  while(!stack1.isEmpty()){
    
	root = stack1.removeLast();
	if(root.left != null)stack1.addLast(root.left);
	if(root.right != null)stack1.addLast(root.right);
	stack2.addLast(root);
  }
  while(!stack2.isEmpty()){
    
    TreeNode node = stack2.removeLast();
    System.out.print(node.val + " ");
  } 
  
}

---

测试：

public static void main(String[] args) {
    
        TreeNode root = new TreeNode(1);
        TreeNode left = new TreeNode(2);
        TreeNode right = new TreeNode(3);
        root.left = left;
        root.right = right;

        System.out.println("前序遍历结果：");
        preOrder(root);

        System.out.println();
        System.out.println("中序遍历结果：");
        inOrder(root);

        System.out.println();
        System.out.println("后序遍历结果：");
        postOrder(root)
}

---

(完)