102. 二叉树的层次遍历

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

解法一：队列

思路：经典的队列问题，使用queue数据结构

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import queue
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        res = []
        q = queue.Queue()
        q.put(root)
        while q.qsize() > 0:  #队列非空时，每次遍历一层
            n = q.qsize()  #该层大小
            data = []  #该层数据
            for i in range(n):  #遍历该层
                node = q.get()   #从队列中取出结点
                data.append(node.val)  #记录数据
                #左右子入队
                if node.left:
                    q.put(node.left)
                if node.right:
                    q.put(node.right)
            res.append(data)
        return res

其实熟练之后可以用list代替队列，速度更快：

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        res = []
        queue = [root]
        while queue:  #队列非空时，每次遍历一层
            data = []  #该层数据
            for i in range(len(queue)):  #遍历该层
                node = queue.pop(0)   #从队列头取出结点
                data.append(node.val)  #记录数据
                #左右子入队
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(data)
        return res

js: 队列通过数组的push在尾部插入，shift从头部取出实现

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
  if (root === null) return []
  const res = []
  const queue = []
  queue.push(root)
  while (queue.length > 0) {
    const count = queue.length
    const data = []
    for (let i = 0; i < count; i++) {
      const node = queue.shift()
      data.push(node.val)
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }
    res.push(data)
  }
  return res
};