二叉树遍历（非递归版）

基本概念

• 前序遍历：先访问根节点，再访问左子节点，最后访问右子节点
• 中序遍历：先访问左子节点，再访问跟节点，最后访问右子节点
• 后序遍历：先访问左子节点，再访问右子节点，最好访问根节点

前序遍历

要想用非递归的方式解决问题，几乎都是采用栈的方式解决。前序遍历是先访问根节点，再访问左子节点，最后访问右子节点，对应图中顺序1->2->4->5->3->6->7.所以我们可以采用以下方式来做：

• 假设cur=head，将cur入栈
• 不断从栈中弹出栈顶节点，然后把右子节点和左子节点放入栈中（因为先访问左子节点，栈为先进后出的数据结构，所以先放左子节点）
• 当栈不为空，不断重复上一步骤

代码如下

public void preOrderUnRecur(Node node){
        System.out.println("非递归前序遍历");
        if (node == null) return;
        Stack<Node> stack = new Stack<>();
        stack.push(node);
        while (!stack.empty()){
            Node curNode = stack.pop();
            System.out.print(curNode.value+" ");
            if (curNode.right != null) stack.push(curNode.right);
            if (curNode.left != null) stack.push(curNode.left);
        }
        System.out.println();
    }

中序遍历

中序遍历的顺序是先左子节点，再当前节点，再右子节点，对应图中4->2->5->1->6->3->7.解题思路如下

• 初始化cur=head
• 将cur入栈，不断将cur=cur.left(不断取左子节点)，重复当前过程
• 如果发现cur为空，则说明已经访问到“最左“节点，出栈并打印当前节点的值，将其右子节点赋值给cur，重复上一步

代码如下：

public void inOrderUnRecur(Node node){
        if (node == null) return;
        Stack<Node> stack = new Stack<>();
        while (!stack.empty() || node != null){
            if (node != null){
                stack.push(node);
                node = node.left;
            }else {
                node = stack.pop();
                System.out.println(node.value);
                node = node.right;
            }
        }
    }

后序遍历

后序遍历的访问顺序为先左子节点，再右子节点，最后访问当前节点，对应于图中的4->5->2->6->7->3->1,后序遍历比较难，我这里提供一种双栈的解决思路。想一下怎么能做到先左再右最后中呢？要想做到这一点，根节点要在栈底，然后是右子节点，最后是左子节点。我们可以采用如下方式做到这一点

• 申请两个栈s1,s2,将头节点压入s1
• 从s1中弹出节点cur依次将cur的做孩子右孩子压入s1，同时将cur压入栈s2中
• 最后s2的栈即为访问顺序，不断弹出打印即可

代码如下

public void posOrderUnRecur(Node node){
        Stack<Node> stack1 = new Stack<>();
        Stack<Node> stack2 = new Stack<>();

        stack1.push(node);

        while (!stack1.empty()){
            node = stack1.pop();
            stack2.push(node);
            if (node.left != null){
                stack1.push(node.left);
            }
            if (node.right != null){
                stack1.push(node.right);
            }
        }
        while (!stack2.empty()){
            System.out.println(stack2.pop().value);
        }
    }