题目描述

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入： root = [3,9,20,null,null,15,7]
输出： [[3],[9,20],[15,7]]

示例 2：

输入： root = [1]
输出： [[1]]

示例 3：

输入： root = []
输出： []

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

代码及注释

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func levelOrder(root *TreeNode) [][]int {
    // 初始化结果数组和当前层的节点值数组
    var res [][]int
    var ans []int
    // 定义一个栈用于存储当前层的节点
    var stack []*TreeNode

    // 如果根节点为空，直接返回空数组
    if root == nil {
        return res
    }
    // 将根节点入栈
    stack = append(stack, root)

    // 开始层序遍历
    for len(stack) > 0 {
        // 获取当前层的节点数量
        length := len(stack)
        // 遍历当前层的所有节点
        for i := 0; i < length; i++ {
            root = stack[i]
            // 将当前节点的值加入到当前层的节点值数组
            ans = append(ans, root.Val)
            // 如果当前节点有左子节点，将左子节点入栈
            if root.Left != nil {
                stack = append(stack, root.Left)
            } 
            // 如果当前节点有右子节点，将右子节点入栈
            if root.Right != nil {
                stack = append(stack, root.Right)
            }
        }
        // 将当前层的节点值数组加入到结果数组
        res = append(res, ans)
        // 重置当前层的节点值数组
        ans = []int{}
        // 更新栈，去除已经遍历的当前层节点
        stack = stack[length:]
    }
    // 返回结果数组
    return res
}

代码解释

1. 初始化：首先，我们初始化一个空的二维数组 res 用于存储结果，一个空的数组 ans 用于存储当前层的节点值，以及一个栈 stack 用于存储当前层的节点。

2. 判断根节点：如果根节点为空，直接返回空的结果数组。

3. 层序遍历：

   • 使用一个 for 循环遍历栈中的节点，直到栈为空。
   • 在每一次迭代开始时，我们获取当前栈的长度，这是为了遍历当前层的所有节点。
   • 在内部的 for 循环中，我们将当前节点的值添加到 ans 数组中，并将其左右子节点（如果存在）添加到栈中。
   • 将 ans 数组添加到 res 数组中，表示当前层的节点值。
   • 重置 ans 数组为一个空数组，以便下一层使用。
   • 更新栈，去除已经遍历的当前层的节点。

4. 返回结果：返回层序遍历的结果 res。