LeetCode 102. 二叉树的层序遍历

Categories:

Tags:

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

题目描述

🔥 102. 二叉树的层序遍历

思路分析

理解层序遍历：

层序遍历是指从上到下、从左到右逐层遍历二叉树的节点。

使用队列（Queue）：

队列是一种先进先出（FIFO）的数据结构，非常适合用于层序遍历。

用队列来存储每一层的节点，然后逐层处理。

具体步骤：

初始化：创建一个队列，并将根节点（如果存在）加入队列。

遍历每一层：

获取当前队列的长度，这个长度代表当前层的节点数。

遍历当前层的所有节点，将它们的值加入到当前层的结果列表中。

将当前层的所有子节点（左子节点和右子节点）加入队列，以便在下一次循环中处理。

重复上述步骤，直到队列为空。

最后，返回所有层的结果列表。

参考代码

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func levelOrder(root *TreeNode) [][]int {
	var res [][]int
	if root == nil {
		return res
	}

	queue := []*TreeNode{root}

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

		for i := 0; i < levelSize; i++ {
			node := queue[0]
			queue = queue[1:]
			currentLevel = append(currentLevel, node.Val)

			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}

		res = append(res, currentLevel)
	}

	return res
}

🍏 点击查看 Java 题解

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            res.add(level);
        }
        return res;
    }
}

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/87203213