【剑指offer】面试题32：从上到下打印二叉树

旧城等待， 2022-03-29 09:17 203阅读 0赞

> **题目1：不分行从上到下打印二叉树。从上往下打印出二叉树的每个节点，同一层的节点从左到右的顺序打印。**

牛客网链接：[https://www.nowcoder.com/questionTerminal/7fe2212963db4790b57431d9ed259701][https_www.nowcoder.com_questionTerminal_7fe2212963db4790b57431d9ed259701]

例如输入下图的二叉树，则依次打印出：8，6，10，5，7，9，11。

![20190108093729727.png][]

这道题实质上考察的就是树的遍历算法，只是这种遍历不是我们熟悉的前序、中序或者后序遍历。由于我们不太熟悉这种按层遍历的方法，可能一下子也想不清楚遍历的过程。

因为按层打印的顺序决定应该先打印的根节点，所以我们从树的根节点开始分析。为了接下来能够打印8的结点的两个子节点，我们应该在遍历到该结点时把值为6和10的两个结点保存到一个容器中，现在容器内就有两个结点了。按照从左到右打印的要求，我们先取出值为6的结点。打印出6后把它的值分别为5和7的两个结点放入数据容器。此时数据容器中有3个结点，值分别为10，5，7。接下来我们从数据容器中取出值为10的结点。注意到值为10的结点比值为5、7的结点先放入容器，此时又比这两个结点先取出，这就是我们通常说的\*\*先入先出\*\*，因此不难看出这个容器应该是一个\*\*队列\*\*。由于值为5，7，9，11的结点都没有子节点，因此只要依次打印即可。

通过分析具体例子，我们可以找到从上到下打印二叉树的规律：**每次打印一个结点的时候，如果该节点有子节点，把该节点的子节点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的节点，重复前面打印操作，直到队列中所有的节点都被打印出来。**

代码实现：

package com.zju.offer.tree;
    import java.util.ArrayList;
    
    /**
     * 不分行从上到下打印二叉树
     * 从上往下打印出二叉树的每个节点，同一层的节点从左到右的顺序打印
     */
    public class PrintFromTopToBottom {
    
    	public class TreeNode {
    	    int val = 0;
    	    TreeNode left = null;
    	    TreeNode right = null;
    
    	    public TreeNode(int val) {
    	        this.val = val;
    	    }
    	}
    	
    	public ArrayList<Integer> printFromTopToBottom(TreeNode root){
    		ArrayList<Integer> list = new ArrayList<>();
    		// 模拟一个队列，也可以用LinkedList
    		ArrayList<TreeNode> queue = new ArrayList<>();
    		
    		if(root == null){
    			return list;
    		}
    		
    		queue.add(root);
    		while(queue.size() != 0){
    			// 将queue中第一个元素移除
    			TreeNode temp = queue.remove(0);
    			// 如果将要移除的节点有左子节点，则加入queue
    			if(temp.left != null){
    				queue.add(temp.left);
    			}
    			// 如果将要移除的节点有右子节点，则加入queue
    			if(temp.right != null){
    				queue.add(temp.right);
    			}
    			// 将temp的值加入list中
    			list.add(temp.val);
    		}
    		return list;
    	}
    }

本题实现代码中用的是一个ArrayList集合去模拟的队列，每次移除下标为0的元素即为队列的头元素，也符合队列“先进先出的特点”。

![20190108105202217.png][]

本题扩展：**如何广度优先遍历一幅有向图？同样也可以基于队列实现。树是图的一种特殊退化形式，从上到下按层遍历二叉树，从本质上来说就是广度优先遍历二叉树。**

> **举一反三：不管是广度优先遍历一幅有向图还是一棵树，都要用到队列。首先把起始节点（对树而言是根节点）放入队列。接下来每次从队列的头部取出一个节点，遍历这个节点之后把它能到达的节点（对树而言是子节点）都依次放入到队列。重复这个遍历过程，直到队列中的节点全部被遍历为止。**

> **题目2：分行从上到下打印二叉树。从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。**

如下案例所示：

![20190108093729727.png][]

打印结果为：

> 8
> 
> 6     10
> 
> 5      7       9      11

这道题和前面的题类似，也可以用一个队列来保存将要打印的节点。**为了把二叉树的每一行单独打印到一行里，我们需要两个变量：一个变量表示在当前层中还没有打印的节点数；另外一个变量表示下一层节点的数目。**

public class PrintFromTopToBottom {
    
    	public class TreeNode {
    	    int val = 0;
    	    TreeNode left = null;
    	    TreeNode right = null;
    
    	    public TreeNode(int val) {
    	        this.val = val;
    	    }
    	}
    	
    	public ArrayList<Integer> printFromTopToBottom_Method1(TreeNode root){
    		ArrayList<Integer> list = new ArrayList<>();
    		// 模拟一个队列，也可以用LinkedList
    		ArrayList<TreeNode> queue = new ArrayList<>();
    		
    		if(root == null){
    			return list;
    		}
    		
    		queue.add(root);
    		int nextLevel = 0;
    		int toBePrinted = 1;
    		
    		while(queue.size() != 0){
    			// 将queue中第一个元素移除
    			TreeNode temp = queue.remove(0);
    			// 如果将要移除的节点有左子节点，则加入queue
    			if(temp.left != null){
    				queue.add(temp.left);
    				nextLevel++;
    			}
    			// 如果将要移除的节点有右子节点，则加入queue
    			if(temp.right != null){
    				queue.add(temp.right);
    				nextLevel++;
    			}
    			// 将temp的值加入list中
    			list.add(temp.val);
    			System.out.print(temp.val + "  ");
    			--toBePrinted;
    			
    			if(toBePrinted == 0){
    				System.out.println();
    				toBePrinted = nextLevel;
    				nextLevel = 0;
    			}
    		}
    		return list;
    	}
    	
    	// 测试
    	public static void main(String[] args) {
    		PrintFromTopToBottom p = new PrintFromTopToBottom();
    		TreeNode root = p.new TreeNode(8);
    		TreeNode node1 = p.new TreeNode(6);
    		TreeNode node2 = p.new TreeNode(10);
    		TreeNode node3 = p.new TreeNode(5);
    		TreeNode node4 = p.new TreeNode(7);
    		TreeNode node5 = p.new TreeNode(9);
    		TreeNode node6 = p.new TreeNode(11);
    		
    		root.left = node1;
    		root.right = node2;
    		node1.left = node3;
    	        node1.right = node4;
    	        node2.left = node5;
    	        node2.right = node6;
    	    
    	        p.printFromTopToBottom_Method1(root);
    	}
    }

变量 toBePrinted 表示在当前层中还没有打印的节点数，而变量 nextLevel 表示下一层的节点数。如果一个节点有子节点，则每把一个子节点加入队列，同时把变量 nextLevel 加1。每打印一个节点，toBePrinted 减 1。当 toBePrinted 变成 0 时，表示当前层的所有节点已经打印完毕，可以继续打印下一层。

> **题目3：之字形打印二叉树。**
> 
> **请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。**

按之字形顺序打印二叉树需要**两个栈**。我们在打印某一层的节点时，把下一层的子节点保存到相应的栈里。如果当前打印的是奇数层（第一层、第三层等），则先保存左子节点再保存右子节点到第一个栈里（因为栈的后进先出特点）；如果当前打印的是偶数层（第二层、第四层等），则先保存右子节点再保存左子节点到第二个栈里。接下来逐个把位于栈顶的节点弹出栈并打印即可。

使用嵌套集合类型来保存 stack1 和 stack2 中弹出的数据，每一个内层小集合中保存一层的数据。

package com.zju.offer.tree;
    import java.util.ArrayList;
    import java.util.Stack;
    
    public class PrintFromTopToBottom {
    
    	public class TreeNode {
    	    int val = 0;
    	    TreeNode left = null;
    	    TreeNode right = null;
    
    	    public TreeNode(int val) {
    	        this.val = val;
    	    }
    	}
    	
    	/**
    	 * 之字形打印：奇数从左往右打印、偶数从右往左打印
    	 */
    	public ArrayList<ArrayList<Integer>> Print(TreeNode root){
    		// 层数索引
    		int layer = 1;   
    		// stack1 保存奇数层节点
    		Stack<TreeNode> stack1 = new Stack<TreeNode>();
    		stack1.push(root);  // 因为根节点是奇数层，所以将根节点先保存到stack1中
    		// stack2 保存偶数层节点
    		Stack<TreeNode> stack2 = new Stack<TreeNode>();
    		
    		// 采用双层集合，每一个内层集合存储一层数据
    		ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
    
    		while(!stack1.empty() || !stack2.empty()){
    			if(layer % 2 != 0){
    				// 打印奇数层
    				ArrayList<Integer> temp = new ArrayList<Integer>();
    				while(!stack1.empty()){
    					TreeNode node = stack1.pop();
    					if(node != null){
    						temp.add(node.val);
    						System.out.print(node.val + "  ");
    						// 由于当前层是奇数层，所以它的下一层是要从右往左打印
    						// 因此按照栈的"后进先出"的特性，先保存左子节点，再保存右子节点
    						stack2.push(node.left);
    						stack2.push(node.right);
    					}
    				}
    				if(!temp.isEmpty()){
    					list.add(temp);
    					layer++;
    					System.out.println();
    				}
    			}else{
    				// 打印偶数层
    				ArrayList<Integer> temp = new ArrayList<Integer>();
    				while(!stack2.isEmpty()){
    					TreeNode node = stack2.pop();
    					if(node != null){
    						temp.add(node.val);
    						System.out.print(node.val + "  ");
    						// 由于当前层是偶数层，所以它的下一层是要从左往右打印
    						// 因此按照栈的"后进先出"的特性，先保存右子节点，再保存左子节点
    						stack1.push(node.right);
    						stack1.push(node.left);
    					}
    				}
    				if(!temp.isEmpty()){
    					list.add(temp);
    					layer++;
    					System.out.println();
    				}
    			}
    		}
    		return list;
    	}
    	
    	// 测试
    	public static void main(String[] args) {
    		PrintFromTopToBottom p = new PrintFromTopToBottom();
    		TreeNode root = p.new TreeNode(8);
    		TreeNode node1 = p.new TreeNode(6);
    		TreeNode node2 = p.new TreeNode(10);
    		TreeNode node3 = p.new TreeNode(5);
    		TreeNode node4 = p.new TreeNode(7);
    		TreeNode node5 = p.new TreeNode(9);
    		TreeNode node6 = p.new TreeNode(11);
    		
    		root.left = node1;
    		root.right = node2;
    		node1.left = node3;
    	        node1.right = node4;
    	        node2.left = node5;
    	        node2.right = node6;
    	    
    	        p.Print(root);
    	}
    }

[https_www.nowcoder.com_questionTerminal_7fe2212963db4790b57431d9ed259701]: https://www.nowcoder.com/questionTerminal/7fe2212963db4790b57431d9ed259701
[20190108093729727.png]: /images/20220329/23e94fd4fc224196b74cc55f474912cc.png
[20190108105202217.png]: /images/20220329/3a1b03aa1a034c99aee0262012500a21.png