二叉樹(shù)的深度遍歷，是面試考驗(yàn)面試者最基本的算法功底，讓我們一起再溫習(xí)一遍。

二叉樹(shù).png

前序遍歷：遍歷順序?yàn)楦?jié)點(diǎn)-> 左子樹(shù)-> 右子樹(shù) 4 2 1 3 6 5 7
中序遍歷： 遍歷順序?yàn)?左子樹(shù)-> 根節(jié)點(diǎn) -> 右子樹(shù) 1 2 3 4 5 6 7
后序遍歷：遍歷順序?yàn)?左子樹(shù)-> 右子樹(shù)-> 根節(jié)點(diǎn) 1 3 2 5 7 6 4

二叉樹(shù)定義：

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

我們先看看遞歸版該如何遍歷

    // 前序遍歷  遍歷順序?yàn)楦?jié)點(diǎn)-> 左子樹(shù)-> 右子樹(shù)
    public static void preOrder(TreeNode node) {
        if (node != null) {
            System.out.print(node.val+" ");
            preOrder(node.left);
            preOrder(node.right);
        }

    }

    // 中序遍歷  遍歷順序?yàn)?左子樹(shù)-> 根節(jié)點(diǎn) -> 右子樹(shù)
    public static void inOrder(TreeNode node) {
        if (node != null) {
            inOrder(node.left);
            System.out.print(node.val+" ");
            inOrder(node.right);
        }
    }

    // 后序遍歷 遍歷順序?yàn)?左子樹(shù)-> 右子樹(shù)-> 根節(jié)點(diǎn)
    public static void postOrder(TreeNode node) {
        if (node != null) {
            postOrder(node.left);
            postOrder(node.right);
            System.out.print(node.val+" ");
        }
    }

非遞歸版：二叉樹(shù)的深度遍歷 一般借助于棧先進(jìn)后出的特性進(jìn)行遍歷

    // 前序遍歷非遞歸版
    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; // 用變量記錄右子樹(shù)是否已經(jīng)遍歷
        Stack<TreeNode> stack = new Stack<>();
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.peek();
            // 如果沒(méi)有右子樹(shù)或者右子樹(shù)已經(jīng)遍歷 則可以輸出該節(jié)點(diǎn)
            if (node.right == null || node.right == lastVisit) {
                stack.pop();
                System.out.println(node.val);
                lastVisit = node;
                node = null;
            } else
                // 否則處理右子樹(shù)
                node = node.right;
        }
    }