LeetCode 剑指 Offer 32 - I. 从上到下打印二叉树

Categories:

题目描述
思路分析
1. 解法一：层序遍历（推荐）
相似题目

题目描述

✅ 剑指 Offer 32 - I. 从上到下打印二叉树

思路分析

解法一：层序遍历（推荐）

核心思路：

使用队列进行 BFS，按层访问节点。

依次出队并加入结果数组，同时把左右子节点入队。

遍历完成即得到从上到下的节点序列。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数。

空间复杂度：O(n)，队列最多存储一层节点。

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;

class Solution {
    public int[] levelOrder(TreeNode root) {
        if (root == null) {
            return new int[0];
        }

        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);

        ArrayList<Integer> list = new ArrayList<>();

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            list.add(node.val);

            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }

        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }

        return res;
    }
}

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

	queue := make([]*TreeNode, 0)
	queue = append(queue, root)

	res := make([]int, 0)

	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]

		res = append(res, node.Val)

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

	return res
}

相似题目

题目	难度	考察点
102. 二叉树的层序遍历	中等	BFS
107. 二叉树的层序遍历 II	中等	BFS
199. 二叉树的右视图	中等	BFS
剑指 Offer 32 - I. 从上到下打印二叉树	中等	BFS
103. 二叉树的锯齿形层序遍历	中等	BFS

本文作者: HGNULB

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