LeetCode 107. 二叉树的层序遍历 II

Categories:

题目描述
思路分析
参考代码

题目描述

🔥 107. 二叉树的层序遍历 II

思路分析

层序遍历

参考代码

func levelOrderBottom(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{}
	}

	var res [][]int
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		levelSize := len(queue)
		var level []int

		for i := 0; i < levelSize; i++ {
			// 弹出队首节点
			node := queue[0]
			queue = queue[1:]

			// 将当前节点值加入当前层
			level = append(level, node.Val)

			// 左子节点入队
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			// 右子节点入队
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}

		// 将当前层加入结果集
		res = append(res, level)
	}

	// 反转结果集
	for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
		res[i], res[j] = res[j], res[i]
	}

	return res
}

时间复杂度：O(N)，其中 N 是二叉树的节点数。每个节点遍历一次。

空间复杂度：O(W)，其中 W 是树的最大宽度，队列的最大长度。

🍏 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/34466363