面试题32.2：把二叉树打印成多行

题目描述

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

知识点

二叉树，队列

Qiang的思路

这道题和面试题32.1相比，多了分行输出这个要求。在上一题的基础上，这个也很简单实现。因为如果我们在根节点后面添加一个行结束的标志位，那么当该行全部遍历完之后，我们只需要把该标志位放到队列的最末端，这样就相当于在第二行最后面又多了一个标志位，那么便可以区分什么时候需要换行了。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if pRoot==None:
            return []
        result=[]
        l=['#', pRoot]
        while l!=['#']:
            c=l.pop(0)
            if c=='#':
                result.append([])
                l.append('#')
                continue
            result[-1].append(c.val)
            if c.left!=None:
                l.append(c.left)
            if c.right!=None:
                l.append(c.right)
        return result

因为我需要判断什么时候给数组增加新行，所以我将标志位放在了行前而不是行后。这个并不影响解题的思路。

需要注意的是，标志位会一直存在在队列中，所以最终的遍历终止条件是当队列中只有标志位时。

Book中的思路

书中对于该题的处理也是在上一题的基础上，增加了两个变量解决的，一个存储着当前行剩余的节点数，另一个变量存储着下一行的节点数。这样便可以知道还需要输出多少节点才能换行，同时在换行时将开始下一行节点数的计数。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        # write code here
        if pRoot == None:
            return []
        res=[[]]
        l=[pRoot]
        c_number=1
        n_number=0
        while len(l)!=0:
            n=l.pop(0)
            res[-1].append(n.val)
            c_number-=1
            if n.left!=None:
                l.append(n.left)
                n_number+=1
            if n.right!=None:
                l.append(n.right)
                n_number+=1
            if c_number==0 and n_number!=0:
                c_number=n_number
                n_number=0
                res.append([])
        return res

作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。