剑指60-把二叉树打印成多行

Posted on | In |

题目描述

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

  • 用队列存储节点，每层末尾做一个标志，这里以符号'n'来表示。
  • 访问末尾节点之后，必然产生新的末尾标志。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, pRoot):
        if pRoot is None:
            return []
        # 用队列存储节点，每层末尾做一个标志，这里以符号'n'来表示。
        # 访问末尾节点之后，必然产生新的末尾标志。
        myqueue = [pRoot, 'n']
        mylist = []
        s_layer = []
        while len(myqueue) != 0:
            node = myqueue.pop(0)
            if node != 'n':
                s_layer.append(node.val)
                if node.left is not None:
                    myqueue.append(node.left)
                if node.right is not None:
                    myqueue.append(node.right)
            if len(myqueue) != 0 and myqueue[0] == 'n':
                mylist.append(s_layer[::])
                s_layer = []
                myqueue.pop(0)
                myqueue.append('n')
        return mylist