代码实现

C++ 版本

#include <bits/stdc++.h>
using namespace std;

// 定义二叉树节点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 构建二叉树
TreeNode* buildTree(const vector<int>& nums) {
    if (nums.empty() || nums[0] == -1) return nullptr;

    vector<TreeNode*> nodes(nums.size(), nullptr);
    for (size_t i = 0; i < nums.size(); i++) {
        if (nums[i] != -1) nodes[i] = new TreeNode(nums[i]);
    }

    for (size_t i = 0; i < nums.size(); i++) {
        if (nodes[i]) {
            if (2 * i + 1 < nums.size()) nodes[i]->left = nodes[2 * i + 1];
            if (2 * i + 2 < nums.size()) nodes[i]->right = nodes[2 * i + 2];
        }
    }
    
    return nodes[0];  // 返回根节点
}

// 层序遍历并输出
void levelOrder(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* curr = q.front();
        q.pop();
        cout << curr->val << endl;
        if (curr->left) q.push(curr->left);
        if (curr->right) q.push(curr->right);
    }
}

int main() {
    string line;
    getline(cin, line); // 读取整行输入
    istringstream iss(line);
    vector<int> nums;
    int val;
    while (iss >> val) {
        nums.push_back(val);
    }

    TreeNode* root = buildTree(nums);
    levelOrder(root);

    return 0;
}

Python 版本

import sys
from collections import deque

class TreeNode:
    """定义二叉树节点"""
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(nums):
    """根据数组构建二叉树"""
    if not nums or nums[0] == -1:
        return None

    nodes = [TreeNode(val) if val != -1 else None for val in nums]
    
    for i in range(len(nums)):
        if nodes[i]:  # 非空节点
            left_idx, right_idx = 2 * i + 1, 2 * i + 2
            if left_idx < len(nums):
                nodes[i].left = nodes[left_idx]
            if right_idx < len(nums):
                nodes[i].right = nodes[right_idx]
    
    return nodes[0]

def level_order(root):
    """层序遍历并输出"""
    if not root:
        return

    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

# 读取输入
nums = list(map(int, sys.stdin.readline().split()))
root = build_tree(nums)
level_order(root)

Java 版本

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Main {
    public static TreeNode buildTree(int[] nums) {
        if (nums.length == 0 || nums[0] == -1) return null;

        TreeNode[] nodes = new TreeNode[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != -1) nodes[i] = new TreeNode(nums[i]);
        }

        for (int i = 0; i < nums.length; i++) {
            if (nodes[i] != null) {
                int leftIdx = 2 * i + 1;
                int rightIdx = 2 * i + 2;
                if (leftIdx < nums.length) nodes[i].left = nodes[leftIdx];
                if (rightIdx < nums.length) nodes[i].right = nodes[rightIdx];
            }
        }

        return nodes[0];
    }

    public static void levelOrder(TreeNode root) {
        if (root == null) return;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.println(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Integer> list = new ArrayList<>();

        while (sc.hasNextInt()) {
            list.add(sc.nextInt());
        }
        sc.close();

        int[] nums = list.stream().mapToInt(i -> i).toArray();
        TreeNode root = buildTree(nums);
        levelOrder(root);
    }
}

解题思路

1. 解析输入

   ：

   • 读取数组 nums，其中 -1 代表空节点。

2. 构建二叉树

   ：

   • 使用数组索引

     i
     

     计算子节点索引：

     • 左子节点：2*i + 1
     • 右子节点：2*i + 2

   • 先构建所有节点（TreeNode），然后按照索引链接子节点。

3. 层序遍历

   ：

   • 使用**队列（BFS）**遍历二叉树，并按顺序输出。

时间复杂度分析

• 构建二叉树：O(n)
• 层序遍历：O(n)
• 总复杂度：O(n)

空间复杂度：

• 需要 O(n) 额外存储节点，因此 O(n)。

题目内容

给定一个整数数组 nums，其中 nums[i] 表示二叉树节点的值。 按照以下规则构建二叉树：

• 根节点：nums[0]
• 左子节点：nums[i] 的左子节点是 nums[2*i + 1]
• 右子节点：nums[i] 的右子节点是 nums[2*i + 2]
• -1 表示 空节点，在构建树时跳过该节点。

你的任务是：

1. 先构造这棵二叉树。
2. 按 层序遍历（BFS） 输出树的所有节点值，每个值占一行。

输入描述

输入一行，包含 若干整数，表示二叉树的层序数组表示。 （可能包含 -1，表示空节点）

输出描述

按照层序遍历输出二叉树的所有节点，每个值占一行。

样例 1

输入

1 2 3 4 5 -1 6

树的结构

       1
      / \
     2   3
    / \   \
   4   5   6

输出

1
2
3
4
5
6

样例 2

输入

5 3 8 -1 4 7 10

树的结构

       5
      / \
     3   8
      \  / \
      4 7  10

输出

5
3
8
4
7
10