剑指 Offer 32 – II. 从上到下打印二叉树 II

题目描述

https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

提示：

节点总数 <= 1000
注意：本题与主站 102 题相同：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

解题思路

层级遍历肯定要用队列啦。python里面队列可以用list实现。
入队操作：

queue.append(num)  # 在最右插入元素

出队操作：

num = queue.pop(0)  # 出最左边的元素

先复习一下传统的层级遍历

class Solution:
    def levelOrder(self, root: TreeNode) -> list[list[int]]:
        result = []
        if root is None:
            return result
        queue = []
        queue.append(root)
        while len(queue) > 0:
            node = queue.pop(0)
            print(node.val)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)

我们的目标是在这个的基础上，让每层的值一起输出。因此，在导入时要将每一层输入的个数记录下来。
第一层：由于当前队列里面只有一个结点，因此只吐出len(queue)=1个结点，此时队列为空（第一层吐完啦）。然后检查这个吐出的结点有没有左右孩子，并加入队列。此时第一层的唯一一个结点已经吐了出来，还有len(queue)=2个结点。
第二层：用for(2)循环分别吐出一下队列里面剩下的2个结点，每吐出一个节点就要在队列中加入该结点的左右孩子结点。
每个while循环（每一层）吐出一个val list，将这个list加入result list就好。

解题代码

python

class Solution:
    def levelOrder(self, root: TreeNode) -> list[list[int]]:
        result = []
        if root is None:
            return result
        queue, result = [], []
        queue.append(root)
        while len(queue) > 0:
            now_level_size = len(queue)
            now_level_result = []
            for _ in range(now_level_size):
                # 分别对本层的元素进行出队操作和孩子入队操作
                node = queue.pop(0)
                now_level_result.append(node.val)
                if node.left is not None:
                    queue.append(node.left)
                if node.right is not None:
                    queue.append(node.right)
            result.append(now_level_result)
        return result

golang

func levelOrder(root *TreeNode) [][]int {
    var result [][]int
    var queue []*TreeNode
    if root == nil {
        return result
    }
    queue = append(queue, root)
    for len(queue) > 0 {
        var nowLevelQueue []int
        nowLevelLength := len(queue)
        for i := 0; i < nowLevelLength; i++ {
            node := queue[0]
            nowLevelQueue = append(nowLevelQueue, node.Val)
            queue = queue[1:]
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        result = append(result, nowLevelQueue)
    }
    return result
}

执行结果

执行结果：通过
执行用时：44 ms, 在所有 Python3 提交中击败了51.23%的用户
内存消耗：15.2 MB, 在所有 Python3 提交中击败了45.11%的用户