二叉树的迭代遍历

递归的实现底层是栈，所以二叉树的遍历也可以用栈来实现

前序遍历

前序遍历顺序是 中左右 ，每次先处理的是根结点，其次加入右结点和左结点。

//利用栈实现
public static void preOrderRecur2(Node root) {
        if (root == null) {
            return;
        }
        Stack<Node> stack = new Stack<Node>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node temp = stack.pop();
            System.out.println(temp.val);
            if (temp.right != null) {
                stack.push(temp.right);
            }
            if (temp.left != null) {
                stack.push(temp.left);
            }
        }
    }

中序遍历

中序遍历的顺序树 左中右

public static void midOrderRecur3(Node root){
        Node temp = root;
        Stack<Node> stack = new Stack<>();
        while (!stack.isEmpty() || temp != null){
            while(temp != null){
                stack.push(temp);
                temp = temp.left;
            }
            if(stack!=null){
                temp = stack.pop();
                System.out.println(temp.val);
                temp = temp.right;
            }
        }

    }

后序遍历

后续遍历的顺序为 左右中 ，利用前序遍历的顺序是中左右 变为中右左放在另一个栈中倒序输出即可

public static void postOrderRecur2(Node root) {
        Stack<Node> stack1 = new Stack<>();
        Stack<Node> stack2 = new Stack<>();
        stack1.push(root);
        while (!stack1.isEmpty()) {
            Node temp = stack1.pop();
            stack2.push(temp);
            if(temp.left!=null){
                stack1.push(temp.left);
            }
            if(temp.right!=null){
                stack1.push(temp.right);
            }
        }
        while (!stack2.isEmpty()) {
            System.out.println(stack2.pop().val);
        }
    }

二叉树的迭代遍历

原文：https://www.cnblogs.com/nj123/p/14611831.html