二叉树的前中后序遍历（递归，非递归版）

二叉树的深度遍历，是面试考验面试者最基本的算法功底，让我们一起再温习一遍。

二叉树.png

前序遍历：遍历顺序为根节点-> 左子树-> 右子树 4 2 1 3 6 5 7
中序遍历： 遍历顺序为 左子树-> 根节点 -> 右子树 1 2 3 4 5 6 7
后序遍历：遍历顺序为 左子树-> 右子树-> 根节点 1 3 2 5 7 6 4

二叉树定义：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    // TreeNode parent;
    public TreeNode(int val) {
        this.val = val;
    }
}

我们先看看递归版该如何遍历

    // 前序遍历  遍历顺序为根节点-> 左子树-> 右子树
    public static void preOrder(TreeNode node) {
        if (node != null) {
            System.out.print(node.val+" ");
            preOrder(node.left);
            preOrder(node.right);
        }

    }

    // 中序遍历  遍历顺序为 左子树-> 根节点 -> 右子树
    public static void inOrder(TreeNode node) {
        if (node != null) {
            inOrder(node.left);
            System.out.print(node.val+" ");
            inOrder(node.right);
        }
    }

    // 后序遍历 遍历顺序为 左子树-> 右子树-> 根节点
    public static void postOrder(TreeNode node) {
        if (node != null) {
            postOrder(node.left);
            postOrder(node.right);
            System.out.print(node.val+" ");
        }
    }

非递归版：二叉树的深度遍历 一般借助于栈先进后出的特性进行遍历

    // 前序遍历非递归版
    public static void preOrderNonRecursion(TreeNode node) {
        Stack<TreeNode> stack = new Stack();
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                System.out.println(node.val);
                node = node.left;
            } else {
                node = stack.pop();
                node = node.right;
            }
        }
    }

    // 中序遍历非递归版
    public static void inOrderNonRecursion(TreeNode node) {

        Stack<TreeNode> stack = new Stack<>();
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                node = stack.pop();
                System.out.println(node.val);
                node = node.right;
            }
        }
    }

    // 后序遍历非递归版
    public static void postOrderNonRecursion(TreeNode node) {

        TreeNode lastVisit = node; // 用变量记录右子树是否已经遍历
        Stack<TreeNode> stack = new Stack<>();
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.peek();
            // 如果没有右子树或者右子树已经遍历 则可以输出该节点
            if (node.right == null || node.right == lastVisit) {
                stack.pop();
                System.out.println(node.val);
                lastVisit = node;
                node = null;
            } else
                // 否则处理右子树
                node = node.right;
        }
    }