剑指59-按之字形顺序打印二叉树

Posted on | In |

题目描述

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

  • 用队列nodeQ来临时存储节点，进而访问其子节点。
  • 队列里两层之间有个要有个标记|，层的奇偶性也要有一个标记issOdd。
    • 访问到该标记时，在队列末尾添加该标记。
  • 要有个缓存nodeLayer来存放同一层访问到的节点值，该层结束时根据奇偶标记来选择输出顺序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def levelrootSnake(root):
    if root is None:
        return []
    # 用队列存储节点，每层末尾做一个标志，这里以符号'n'来表示。
    # 访问末尾节点之后，必然产生新的末尾标志。
    isOdd = True
    myqueue = [root, 'n']
    mylist, nodes_layer = [], []
    while len(myqueue) != 0:
        node = myqueue.pop(0)
        if node != 'n':
            nodes_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':
            if isOdd == True:
                mylist.append(nodes_layer[::])
            else:
                mylist.append(nodes_layer[::-1])
            isOdd = not isOdd
            nodes_layer = []
            myqueue.pop(0)
            myqueue.append('n')
    return mylist

相对于前一个代码用一个数据结构来存储各层的节点，需要两个辅助数据：

  • 对层数是奇、偶，做标记。
  • 两层的分割点，要做标记

想到用两个数据结构来分别存储奇数、偶数层的节点，每个循环内依次对两个数据结构进行处理，不必追踪层数和层间隔。

  • 注意这两个数据结构可以用队列，也可以用栈，其实区别不大。比如前面的代码用数组，后面的代码用栈。
  • 如下代码用的是栈，注意第一个栈先压入左节点，第二个栈先压入右节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    # 返回二维列表[[1,2],[4,5]]
    def Print(self, root):
        if root is None:
            return []
        st1, st2 = [root], []
        res = []
        while len(st1) > 0:
            temp = []
            while len(st1) > 0:
                node = st1.pop(-1)
                temp.append(node.val)
                if node.left:
                    st2.append(node.left)
                if node.right:
                    st2.append(node.right)
            if len(temp) > 0:
                res.append(temp[::])
            temp = []
            while len(st2) > 0:
                node = st2.pop(-1)
                temp.append(node.val)
                if node.right:
                    st1.append(node.right)
                if node.left:
                    st1.append(node.left)
            if len(temp) > 0:
                res.append(temp[::])
        return res