32:從上到下打印二叉樹

習慣github pages風格的請看我的另一篇博客

題目32：從上到下打印二叉樹

  1. 不分行從上到下打印二叉樹
  2. 分行從上到下打印二叉樹
  3. 之字形打印二叉樹

題目 1. 不分行從上到下打印二叉樹

從上到下打印出二叉樹的每個節(jié)點，同一層的節(jié)點按照從左到右的順序打印。

二叉樹結(jié)點

    public static class BinaryTreeNode {
        int value;
        BinaryTreeNode left;
        BinaryTreeNode right;
        public BinaryTreeNode(){
        }
        public BinaryTreeNode(int value){
            this.value = value;
        }
    }

舉例說明

如下的二叉樹

            8
         /     \
        6       10
       /  \      / \
      5   7     9  11

則依次打印出8 6 10 5 7 9 11

解題思路

考查樹的遍歷算法。
從上到下打印二叉樹的規(guī)律：

  1. 每一次打印一個結(jié)點的時候，如果該結(jié)點有子結(jié)點， 則把該結(jié)點的子結(jié)點放到一個隊列的末尾
  2. 接下來到隊列的頭部取出最早進入隊列的結(jié)點
  3. 重復前面的打印操作，直至隊列中所有的結(jié)點都被打印出來為止

代碼實現(xiàn)：

import java.util.Queue;
import java.util.LinkedList;

public class _3200{
    public static class BinaryTreeNode {
        int value;
        BinaryTreeNode left;
        BinaryTreeNode right;
        public BinaryTreeNode(){
        }
        public BinaryTreeNode(int value){
            this.value = value;
        }
    }

    public static void printFromTopToBottom(BinaryTreeNode root) {
        if (root != null) { // 當結(jié)點非空時才進行操作
            // 用于存放還未遍歷的元素
            Queue<BinaryTreeNode> list = new LinkedList<>();
            list.add(root);            //   根結(jié)點入隊
            BinaryTreeNode cur;  //   當前處理的結(jié)點
            while (!list.isEmpty() ) { 
                cur = list.remove(); // 刪除隊首
                System.out.print(cur.value + " ");  //  輸出隊首元素的值
                // 如果左子結(jié)點不為空，則左子結(jié)點入隊
                if (cur.left != null) {
                    list.add(cur.left);
                }
                // 如果右子結(jié)點不為空，則左子結(jié)點入隊
                if (cur.right != null) {
                    list.add(cur.right);
                }
            }
        }
    }

    public static void main(String[] args) {
        //       8
        //    /    \
        //   6     10
        //  / \   / \
        // 5   7 9  11
        BinaryTreeNode n1 = new BinaryTreeNode(8);
        BinaryTreeNode n2 = new BinaryTreeNode(6);
        BinaryTreeNode n3 = new BinaryTreeNode(10);
        BinaryTreeNode n4 = new BinaryTreeNode(5);
        BinaryTreeNode n5 = new BinaryTreeNode(7);
        BinaryTreeNode n6 = new BinaryTreeNode(9);
        BinaryTreeNode n7 = new BinaryTreeNode(11);
        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;
        n3.left = n6;
        n3.right = n7;
        printFromTopToBottom(n1);
    }
}
不分行從上到下打印二叉樹

擴展：

  • 從上到下按層遍歷二叉樹，從本質(zhì)上來說就是廣度優(yōu)先遍歷二叉樹
  • 不管是廣度優(yōu)先遍歷一幅有向圖還是一棵樹，都要用到隊列
  • 首先把起始節(jié)點（樹中為根結(jié)點）放入隊列，接下來每次從隊列的頭部取出一個節(jié)點，遍歷這個節(jié)點后把它能到達的節(jié)點（樹中為子結(jié)點）都依次放入隊列。重復這個遍歷過程，直到隊列中的節(jié)點全部都遍歷為止

題目 2. 分行從上到下打印二叉樹

從上到下按層打印二叉樹，同一層的節(jié)點按從左到右的順序打印，每一層打印到一行。

舉例說明

如下的二叉樹

            8
         /     \
        6       10
       /  \      / \
      5   7     9  11

則依次打印出

8  
6 10 
5 7 9 11

解題思路

用隊列來保存要打印的節(jié)點。
同時我們需要兩個變量：一個變量表示在當前層中還沒有打印的節(jié)點數(shù)；另一個變量表示下一層節(jié)點的數(shù)目

代碼實現(xiàn)

import java.util.LinkedList;
import java.util.List;

public class _3201{
    public static class BinaryTreeNode {
        int value;
        BinaryTreeNode left;
        BinaryTreeNode right;
        public BinaryTreeNode(){
        }
        public BinaryTreeNode(int value){
            this.value = value;
        }
    }

    public static void print(BinaryTreeNode root) {
        if (root == null) {
            return;
        }
        List<BinaryTreeNode> list = new LinkedList<>();
        BinaryTreeNode node;
        int current = 1;// 當前層的結(jié)點個數(shù),開始時只有根節(jié)點一個
        int next = 0;// 下一層的結(jié)點個數(shù)
        list.add(root);
        while (list.size() > 0) {
            node = list.remove(0);
            current--;
            System.out.print(" "+node.value);
            if (node.left != null) {
                list.add(node.left);
                next++;
            }
            if (node.right != null) {
                list.add(node.right);
                next++;
            }
            if (current ==0) {
                System.out.println();//本層打印完了
                current = next;//現(xiàn)在處理下一層
                next = 0;
            }
        }
    }

    public static void main(String[] args) {
        //       8
        //    /    \
        //   6     10
        //  / \   / \
        // 5   7 9  11
        BinaryTreeNode n1 = new BinaryTreeNode(8);
        BinaryTreeNode n2 = new BinaryTreeNode(6);
        BinaryTreeNode n3 = new BinaryTreeNode(10);
        BinaryTreeNode n4 = new BinaryTreeNode(5);
        BinaryTreeNode n5 = new BinaryTreeNode(7);
        BinaryTreeNode n6 = new BinaryTreeNode(9);
        BinaryTreeNode n7 = new BinaryTreeNode(11);
        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;
        n3.left = n6;
        n3.right = n7;
        print(n1);
    }
}
分行從上到下打印二叉樹

題目 3. 之字形打印二叉樹

請實現(xiàn)一個函數(shù)按照之字形打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印，其他行以此類推。（每一層打印到一行。）

舉例說明

如下的二叉樹

            8
         /     \
        6       10
       /  \      / \
      5   7     9  11

則依次打印出

8  
10 6 
5 7 9 11

解題思路

按之字形順序打印二叉樹需要兩個棧。

  • 我們在打印某一行結(jié)點時，把下一層的子結(jié)點保存到相應的棧里
  • 如果當前打印的是奇數(shù)層，則先保存左子結(jié)點再保存右子結(jié)點到一個棧里
  • 如果當前打印的是偶數(shù)層，則先保存右子結(jié)點再保存左子結(jié)點到第二個棧里

代碼實現(xiàn)

import java.util.LinkedList;
import java.util.List;

public class _3202{
    public static class BinaryTreeNode {
        int value;
        BinaryTreeNode left;
        BinaryTreeNode right;
        public BinaryTreeNode(){
        }
        public BinaryTreeNode(int value){
            this.value = value;
        }
    }

    public static void print(BinaryTreeNode root) {
        if (root == null) {
            return;
        }
        List<BinaryTreeNode> current = new LinkedList<>();
        List<BinaryTreeNode> reverse = new LinkedList<>();
        int flag = 0;//bool flag = false;
        BinaryTreeNode node;
        current.add(root);
        while (current.size() > 0) {
            // 從最后一個開始取，相當于棧
            node = current.remove(current.size() - 1);
            System.out.print(" "+node.val);
            if (flag == 0) {// if (!flag )   // 當前是從左往右打印的，那就按從左往右入棧
                if (node.left != null) {
                    reverse.add(node.left);
                }
                if (node.right != null) {
                    reverse.add(node.right);
                }
            }else { // 當前是從右往左打印的，那就按從右往左入棧
                if (node.right != null) {
                    reverse.add(node.right);
                }
                if (node.left != null) {
                    reverse.add(node.left);
                }
            }
            if (current.size() == 0) {//當前層處理完了
                flag = 1 - flag;//flag != ;
                List<BinaryTreeNode> tmp = current;
                current = reverse;
                reverse = tmp;
                System.out.println();
            }
        }
    }

    public static void main(String[] args) {
        //       8
        //    /    \
        //   6     10
        //  / \   / \
        // 5   7 9  11
        BinaryTreeNode n1 = new BinaryTreeNode(8);
        BinaryTreeNode n2 = new BinaryTreeNode(6);
        BinaryTreeNode n3 = new BinaryTreeNode(10);
        BinaryTreeNode n4 = new BinaryTreeNode(5);
        BinaryTreeNode n5 = new BinaryTreeNode(7);
        BinaryTreeNode n6 = new BinaryTreeNode(9);
        BinaryTreeNode n7 = new BinaryTreeNode(11);
        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n2.right = n5;
        n3.left = n6;
        n3.right = n7;
        print(n1);
    }
}
之字形打印二叉樹
最后編輯于 ：
?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內(nèi)容

  • 樹 記錄《劍指offer》中所有關于樹的題目，以及LeetCode中的相似題目。 相關題目列表 題目 樹是一種最常...
    wenmingxing閱讀 1,516評論 2贊 13
  • 一些概念 數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間相互關系，并對這種結(jié)構(gòu)定義相應的運算，而且確保經(jīng)過這...
    Winterfell_Z閱讀 6,603評論 0贊 13
  • 前言 2. 實現(xiàn) Singleton 3. 數(shù)組中重復的數(shù)字 4. 二維數(shù)組中的查找 5. 替換空格 6. 從尾到...
    Observer_____閱讀 3,159評論 0贊 1
  • 前段時間，一直在關注“江歌案” 的進展，案子塵埃落定后，作為一個心理咨詢師，我想從心理學的角度，寫點感想。 ...
    田邊插柳閱讀 2,170評論 0贊 1
  • 我們家向來有喝酒的傳統(tǒng)，遙記小時候，印象中的酒場典型何其多，記憶深刻的有一個中風已經(jīng)半身不遂的大爺爺，每天必然3頓...
    黑土錢閱讀 202評論 3贊 4

友情鏈接更多精彩內(nèi)容