求二叉树的层序遍历

问题简述

层序遍历二叉树，每层的结果单独保存在一个列表中。

求二叉树的层序遍历_牛客题霸_牛客网

思路

• 辅助队列

Python

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型二维数组
#
class Solution:
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        # write code here
        if not root: return []
        
        from collections import deque
        
        ret = []
        q = deque()
        q.append(root)
        cnt = 1
        nxt = 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:
                ret.append(tmp)
                tmp = []
                cnt = nxt
                nxt = 0
        
        return ret