層次遍歷，也就是我們常說的廣度優(yōu)先遍歷

這個相對來說比較簡單，就是一層一層遍歷，核心點是采用隊列，queue

創(chuàng)新互聯(lián)是一家專業(yè)提供隆昌企業(yè)網(wǎng)站建設(shè),專注與成都網(wǎng)站制作、成都做網(wǎng)站、外貿(mào)營銷網(wǎng)站建設(shè)、H5網(wǎng)站設(shè)計、小程序制作等業(yè)務(wù)。10年已為隆昌眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站建設(shè)公司優(yōu)惠進(jìn)行中。

直接上代碼

public static void levelTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        Queuequeue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            System.out.println(poll.value);
            if (poll.left != null) {
                queue.offer(poll.left);
            }
            if (poll.right != null) {
                queue.offer(poll.right);
            }
        }
    }

接下來是深度優(yōu)先遍歷，深度優(yōu)先遍歷分為三種，先序遍歷，中序遍歷，后續(xù)遍歷

而深度優(yōu)先遍歷，核心點是采用棧

先序遍歷的非遞歸寫法，大致有兩種，一種是投機(jī)取巧，一種是標(biāo)準(zhǔn)寫法

直接上代碼，投機(jī)取巧的寫法

public static void preorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        Stackstack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            System.out.println(pop.value);
            if (pop.right != null) {
                stack.push(pop.right);
            }
            if (pop.left != null) {
                stack.push(pop.left);
            }
        }
    }

標(biāo)準(zhǔn)寫法

public static void preorderTraversal02(TreeNode root) {
        if (root == null) {
            return;
        }
        Stackstack = new Stack<>();
        TreeNode temp = root;
        while (temp != null || !stack.isEmpty()) {
            while (temp != null) {
                stack.push(temp);
                System.out.println(temp.value);
                temp = temp.left;
            }
            if (!stack.isEmpty()) {
                TreeNode pop = stack.pop();
                temp = pop.right;
            }
        }
    }

然后是中序遍歷，中序遍歷沒有投機(jī)取巧的方法，只有一種標(biāo)準(zhǔn)寫法

public static void middleorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        Stackstack = new Stack<>();
        TreeNode temp = root;
        while (temp != null || !stack.isEmpty()) {
            while (temp != null) {
                stack.push(temp);
                temp = temp.left;
            }
            if (!stack.isEmpty()) {
                TreeNode pop = stack.pop();
                System.out.println(pop.value);
                temp = pop.right;
            }
        }
    }

后序遍歷，也有兩種寫法，一種投機(jī)取巧，一種標(biāo)準(zhǔn)寫法

投機(jī)取巧的方式，代碼如下

public static void postorderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        Stackstack = new Stack<>();
        stack.push(root);
        Listlist = new LinkedList<>();
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            list.add(pop);
            if (pop.left != null) {
                stack.push(pop.left);
            }
            if (pop.right != null) {
                stack.push(pop.right);
            }
        }
        Collections.reverse(list);
        list.stream().forEach(System.out::println);
    }

標(biāo)準(zhǔn)寫法

public static void postorderTraversal02(TreeNode root) {
        if (root == null) {
            return;
        }
        Stackstack = new Stack<>();
        TreeNode temp = root, lastNode = null;
        while (temp != null || !stack.isEmpty()) {
            while (temp != null) {
                stack.push(temp);
                temp = temp.left;
            }
            // 查看當(dāng)前棧頂元素
            temp = stack.peek();
            // 如果其右子樹也為空，或者右子樹已經(jīng)訪問過，則可以直接輸出當(dāng)前節(jié)點的值
            if (temp.right == null || temp.right == lastNode) {
                System.out.println(temp.value);
                stack.pop();
                // 把輸出的節(jié)點賦值給lastNode游標(biāo)，作為下次比對的依據(jù)
                lastNode = temp;
                temp = null;
            } else {
                // 否則，繼續(xù)遍歷右子樹
                temp = temp.right;
            }
        }
    }

總結(jié)：

廣度優(yōu)先遍歷比較簡單，深度優(yōu)先遍歷，先序與中序標(biāo)準(zhǔn)寫法是相同的代碼結(jié)構(gòu)，只需要一個指針，后續(xù)則不一樣，需要記錄上一次的遍歷節(jié)點，需要兩個指針，總的來說，練習(xí)一下都比較簡單。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前文章：二叉樹遍歷的非遞歸寫法-創(chuàng)新互聯(lián)
URL網(wǎng)址：http://weahome.cn/article/doehsj.html