按之字形顺序打印二叉树

问题简述

层序遍历二叉树，按之字形打印每层。

按之字形顺序打印二叉树_牛客题霸_牛客网

思路

• 队列 + 奇偶讨论，思路比较简单，因为需要把层分离，所以需要借助的辅助变量比较多，详见代码；

Python

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pRoot TreeNode类 
# @return int整型二维数组
#
class Solution:
    def Print(self , pRoot: TreeNode) -> List[List[int]]:
        # write code here
        if not pRoot: return []
        
        from collections import deque
        
        ret = []
        q = deque()
        q.append(pRoot)
        cnt = 1
        nxt = 0  # 下一层需要遍历的节点数
        lv = 0  # 已经遍历的层数
        tmp = []  # 当前层缓存的节点数
        while cnt:
            cnt -= 1
            node = q.popleft()
            tmp.append(node.val)
            
            if node.left:
                q.append(node.left)
                nxt += 1
            if node.right:
                q.append(node.right)
                nxt += 1
            
            if cnt == 0:
                if lv % 2:
                    ret.append(tmp[::-1])
                else:
                    ret.append(tmp)
                tmp = []
                lv += 1
                cnt = nxt
                nxt = 0
                
        return ret