本題來自左神《程序員代碼面試指南》“二叉樹的按層打印與ZigZag打印”題目。

題目

給定一棵二叉樹的頭節(jié)點(diǎn) head，分別實(shí)現(xiàn) 按層 和 ZigZag 打印 二叉樹的函數(shù)。

例如，二叉樹如圖 3-29 所示。

按層打印時，輸出格式必須如下：

Level 1 : 1 Level 2 : 2 3 Level 3 : 4 5 6 Level 4 : 7 8

ZigZag 打印時，輸出格式必須如下：

Level 1 from left to right: 1 Level 2 from right to left: 3 2 Level 3 from left to right: 4 5 6 Level 4 from right to left: 8 7

---

題解

1、按層打印的實(shí)現(xiàn)

按層打印原本是十分基礎(chǔ)的內(nèi)容，對二叉樹做簡單的寬度優(yōu)先遍歷即可，但本題有額外的要求，那就是 同一層的節(jié)點(diǎn)必須打印在一行上，并且要求輸出行號。這就需要我們在原來寬度優(yōu)先遍歷的基礎(chǔ)上做一些改進(jìn)，所以關(guān)鍵問題是如何知道該換行。

只需要用兩個 node 類型的變量 last 和 nLast 就可以解決這個問題，last 變量表示正在打印的當(dāng)前行的最右節(jié)點(diǎn)，nLast 表示下一行的最右節(jié)點(diǎn)。

假設(shè)我們每一層都做從左到右的寬度優(yōu)先遍歷，如果發(fā)現(xiàn)遍歷到的節(jié)點(diǎn)等于 last，則說明應(yīng)該換行。換行之后，只要令 last=nLast，就可以繼續(xù)下一行的打印過程，重復(fù)此過程，直到所有的節(jié)點(diǎn)都打印完。那么問題就變成了：如何更新 nLast？只需要讓 nLast 一直跟蹤記錄寬度優(yōu)先隊(duì)列中的最新加入的節(jié)點(diǎn)即可。這是因?yàn)樽钚录尤腙?duì)列的節(jié)點(diǎn)一定是目前已經(jīng)發(fā)現(xiàn)的下一行的最右節(jié)點(diǎn)。所以在當(dāng)前行打印完時，nLast 一定是下一行所有節(jié)點(diǎn)中的最右節(jié)點(diǎn)。

public static void printByLevel(Node head) {if (head == null) {return;}Queue<Node> queue = new LinkedList<Node>();int level = 1;Node last = head; // 當(dāng)前行的最右節(jié)點(diǎn)Node nLast = null; // 下一行的最右節(jié)點(diǎn)queue.offer(head);System.out.print("Level " + (level++) + " : ");while (!queue.isEmpty()) { // 每一層都做從左到右寬度優(yōu)先遍歷head = queue.poll();System.out.print(head.value + " ");if (head.left != null) {queue.offer(head.left);nLast = head.left; // 讓nLast一直跟蹤記錄寬度優(yōu)先隊(duì)列中的最新加入的節(jié)點(diǎn)即可，因?yàn)樽钚录尤腙?duì)列的節(jié)點(diǎn)一定是目前已經(jīng)發(fā)現(xiàn)的下一行的最右節(jié)點(diǎn)}if (head.right != null) {queue.offer(head.right);nLast = head.right;}if (head == last && !queue.isEmpty()) { // 如果發(fā)現(xiàn)遍歷到的節(jié)點(diǎn)等于last，則說明應(yīng)該換行System.out.print("\nLevel " + (level++) + " : ");last = nLast; // 當(dāng)前行打印完時，nLast一定是下一行所有節(jié)點(diǎn)中的最右節(jié)點(diǎn)，只要令last=nLast，就可以繼續(xù)下一行的打印過程}}System.out.println(); }

2、ZigZag 打印的實(shí)現(xiàn)

使用一個雙端隊(duì)列，具體為 Java 中的 LinkedList 結(jié)構(gòu)，這個結(jié)構(gòu)的底層實(shí)現(xiàn)就是非常純粹的雙端隊(duì)列結(jié)構(gòu)，本方法也僅使用雙端隊(duì)列結(jié)構(gòu)的基本操作。

原則1：如果是從左到右的過程,那么一律從 dq 的頭部彈出節(jié)點(diǎn)

• 如果彈出的節(jié)點(diǎn)沒有孩子節(jié)點(diǎn)，當(dāng)然不用放入任何節(jié)點(diǎn)到 dq 中
• 如果當(dāng)前節(jié)點(diǎn)有孩子節(jié)點(diǎn)，先讓左孩子節(jié)點(diǎn)從尾部進(jìn)入 dq，再讓右孩子節(jié)點(diǎn)從尾部進(jìn)入dq

原則2：如果是從右到左的過程，那么一律從 dq 的尾部彈出節(jié)點(diǎn)

• 如果彈出的節(jié)點(diǎn)沒有孩子節(jié)點(diǎn)，當(dāng)然不用放入任何節(jié)點(diǎn)到 dq 中
• 如果當(dāng)前節(jié)點(diǎn)有孩子節(jié)點(diǎn)，先讓右孩子從頭部進(jìn)入 dq，再讓左孩子節(jié)點(diǎn)從頭部進(jìn)入 dq

用 原則1 和 原則2 的過程切換，我們可以完成 ZigZag 的打印過程，所以現(xiàn)在只剩一個問題：如何確定切換原則1和原則2的時機(jī)？這其實(shí)還是 如何確定每一層最后一個節(jié)點(diǎn)的問題。具體方法見代碼中的詳細(xì)注釋。

ZigZag 打印的全部過程請參看如下代碼中的 printByZigZag 方法。

---

代碼

含測試用例

package chapter_3_binarytreeproblem;import java.util.Deque; import java.util.LinkedList; import java.util.Queue;public class Problem_09_PrintBinaryTreeByLevelAndZigZag {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}/*** 二叉樹的按層打印*/public static void printByLevel(Node head) {if (head == null) {return;}Queue<Node> queue = new LinkedList<Node>();int level = 1;Node last = head; // 當(dāng)前行的最右節(jié)點(diǎn)Node nLast = null; // 下一行的最右節(jié)點(diǎn)queue.offer(head);System.out.print("Level " + (level++) + " : ");while (!queue.isEmpty()) { // 每一層都做從左到右寬度優(yōu)先遍歷head = queue.poll();System.out.print(head.value + " ");if (head.left != null) {queue.offer(head.left);nLast = head.left; // 讓nLast一直跟蹤記錄寬度優(yōu)先隊(duì)列中的最新加入的節(jié)點(diǎn)即可，因?yàn)樽钚录尤腙?duì)列的節(jié)點(diǎn)一定是目前已經(jīng)發(fā)現(xiàn)的下一行的最右節(jié)點(diǎn)}if (head.right != null) {queue.offer(head.right);nLast = head.right;}if (head == last && !queue.isEmpty()) { // 如果發(fā)現(xiàn)遍歷到的節(jié)點(diǎn)等于last，則說明應(yīng)該換行System.out.print("\nLevel " + (level++) + " : ");last = nLast; // 當(dāng)前行打印完時，nLast一定是下一行所有節(jié)點(diǎn)中的最右節(jié)點(diǎn)，只要令last=nLast，就可以繼續(xù)下一行的打印過程}}System.out.println();}/*** ZigZag 打印的實(shí)現(xiàn)*/public static void printByZigZag(Node head) {if (head == null) {return;}Deque<Node> dq = new LinkedList<Node>();int level = 1;boolean left2right = true; // 是否是從左到右打印過程Node last = head; // 當(dāng)前行的最右節(jié)點(diǎn)Node nLast = null; // 下一行的最右節(jié)點(diǎn)dq.offerFirst(head);pringLevelAndOrientation(level++, left2right);while (!dq.isEmpty()) {if (left2right) { // 【原則1】：如果是從左到右的過程，那么一律從dq的頭部彈出節(jié)點(diǎn)head = dq.pollFirst();// 如果當(dāng)前節(jié)點(diǎn)有孩子節(jié)點(diǎn)，先讓左孩子節(jié)點(diǎn)從尾部進(jìn)入dq，再讓右孩子節(jié)點(diǎn)從尾部進(jìn)入dqif (head.left != null) {// 區(qū)別于"按層打印"，此處的"zigzag打印"的特點(diǎn)為：下一層最后打印的節(jié)點(diǎn)是當(dāng)前層有孩子節(jié)點(diǎn)的節(jié)點(diǎn)中最先進(jìn)入dq的節(jié)點(diǎn)nLast = (nLast == null ? head.left : nLast); // 如果nlast非空，則保持其為"最先"進(jìn)入dq的節(jié)點(diǎn)，不更新dq.offerLast(head.left);}if (head.right != null) {nLast = (nLast == null ? head.right : nLast);dq.offerLast(head.right);}} else { // 【原則2】：如果是從右到左的過程，那么一律從dq的尾部彈出節(jié)點(diǎn)head = dq.pollLast();// 如果當(dāng)前節(jié)點(diǎn)有孩子節(jié)點(diǎn)，先讓右孩子從頭部進(jìn)入dq，再讓左孩子節(jié)點(diǎn)從頭部進(jìn)入dqif (head.right != null) {nLast = (nLast == null ? head.right : nLast);dq.offerFirst(head.right);}if (head.left != null) {nLast = (nLast == null ? head.left : nLast);dq.offerFirst(head.left);}}System.out.print(head.value + " ");// 如何確定切換【原則1】和【原則2】的時機(jī)？這其實(shí)還是如何確定每一層最后一個節(jié)點(diǎn)的問題// 下一層最后打印的節(jié)點(diǎn)是當(dāng)前層有孩子節(jié)點(diǎn)的節(jié)點(diǎn)中最先進(jìn)入dq的節(jié)點(diǎn)if (head == last && !dq.isEmpty()) {left2right = !left2right;last = nLast;nLast = null; // 換行之后置空nLast，與上面的非空判斷配合，保證其為"最先"進(jìn)入dq的節(jié)點(diǎn)System.out.println();pringLevelAndOrientation(level++, left2right);}}System.out.println();}public static void pringLevelAndOrientation(int level, boolean lr) {System.out.print("Level " + level + " from ");System.out.print(lr ? "left to right: " : "right to left: ");}// for test -- print treepublic static void printTree(Node head) {System.out.println("Binary Tree:");printInOrder(head, 0, "H", 17);System.out.println();}public static void printInOrder(Node head, int height, String to, int len) {if (head == null) {return;}printInOrder(head.right, height + 1, "v", len);String val = to + head.value + to;int lenM = val.length();int lenL = (len - lenM) / 2;int lenR = len - lenM - lenL;val = getSpace(lenL) + val + getSpace(lenR);System.out.println(getSpace(height * len) + val);printInOrder(head.left, height + 1, "^", len);}public static String getSpace(int num) {String space = " ";StringBuffer buf = new StringBuffer("");for (int i = 0; i < num; i++) {buf.append(space);}return buf.toString();}public static void main(String[] args) {Node head = new Node(1);head.left = new Node(2);head.right = new Node(3);head.left.left = new Node(4);head.right.left = new Node(5);head.right.right = new Node(6);head.right.left.left = new Node(7);head.right.left.right = new Node(8);printTree(head);System.out.println("===============");printByLevel(head);System.out.println("===============");printByZigZag(head);} }

輸出結(jié)果：

Binary Tree:v6v v3v v8v ^5^ ^7^ H1H ^2^ ^4^ =============== Level 1 : 1 Level 2 : 2 3 Level 3 : 4 5 6 Level 4 : 7 8 =============== Level 1 from left to right: 1 Level 2 from right to left: 3 2 Level 3 from left to right: 4 5 6 Level 4 from right to left: 8 7

總結(jié)

以上是生活随笔為你收集整理的左神算法：二叉树的按层打印与ZigZag打印（Java版）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。