二叉树的层序遍历

题解思路

本题要求对二叉树进行层序遍历，即按照从上到下、从左到右的顺序逐层访问所有节点。可以使用 广度优先搜索（BFS） 来实现，这是一种常见的树的遍历方式。

具体步骤

1. 构造二叉树：

   • 由于输入是按层序给出的数组，我们可以用 数组索引映射 来构造二叉树：
     • 根节点是 root[0]
     • 左子节点的索引为 2*i + 1
     • 右子节点的索引为 2*i + 2
   • 通过队列 逐层构造 树结构。

2. 层序遍历（BFS）：

   • 使用 队列（Queue） 进行广度优先搜索。
   • 每次从队列取出当前层的所有节点，输出其值，并将其左右子节点（如果存在）加入队列。
   • 处理完一层后，换行并继续遍历下一层。

时间复杂度分析

• 构造二叉树 需要遍历输入数组一次，时间复杂度为 O(n)。
• 层序遍历 需要访问每个节点一次，时间复杂度为 O(n)。
• 总复杂度 为 O(n)。

代码实现

Python 代码

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

def build_tree(level_order):
    if not level_order or level_order[0] == 'null':
        return None
    
    root = TreeNode(int(level_order[0]))
    queue = [root]
    i = 1
    while i < len(level_order):
        current = queue.pop(0)
        # 构造左子节点
        if i < len(level_order) and level_order[i] != 'null':
            current.left = TreeNode(int(level_order[i]))
            queue.append(current.left)
        i += 1
        # 构造右子节点
        if i < len(level_order) and level_order[i] != 'null':
            current.right = TreeNode(int(level_order[i]))
            queue.append(current.right)
        i += 1
    return root

def level_order_traversal(root):
    if not root:
        return []
    res = []
    queue = [root]
    while queue:
        level_size = len(queue)
        level_vals = []
        for _ in range(level_size):
            node = queue.pop(0)
            level_vals.append(str(node.val))
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        res.append(" ".join(level_vals))
    return res

if __name__ == "__main__":
    # 输入处理：输入字符串，以空格分隔，构造节点列表
    input_str = input().strip()
    nodes = input_str.split()
    # 构造二叉树
    root = build_tree(nodes)
    # 层次遍历打印结果
    result = level_order_traversal(root)
    for line in result:
        print(line)

Java 代码

import java.util.*;

public class Main {
    // 定义二叉树节点类
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) {
            this.val = val;
        }
    }
    
    // 构造二叉树
    public static TreeNode buildTree(String[] levelOrder) {
        if (levelOrder.length == 0 || levelOrder[0].equals("null"))
            return null;
        
        List<TreeNode> nodes = new ArrayList<>();
        int index = 0;
        TreeNode root = new TreeNode(Integer.parseInt(levelOrder[index]));
        nodes.add(root);
        index++;
        
        while (index < levelOrder.length) {
            String nodeVal = levelOrder[index];
            if (!nodeVal.equals("null")) {
                TreeNode node = new TreeNode(Integer.parseInt(nodeVal));
                TreeNode parent = nodes.get((index - 1) / 2);
                if (index % 2 == 1)
                    parent.left = node;
                else
                    parent.right = node;
                nodes.add(node);
            }
            index++;
        }
        return root;
    }
    
    // 层次遍历并输出每层结果
    public static List<String> levelOrderTraversal(TreeNode root) {
        List<String> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                sb.append(node.val);
                if (i < levelSize - 1) {
                    sb.append(" ");
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            res.add(sb.toString());
        }
        return res;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 输入处理：以空格分隔
        String line = sc.nextLine().trim();
        String[] nodes = line.split("\\s+");
        // 构造二叉树
        TreeNode root = buildTree(nodes);
        // 层次遍历输出结果
        List<String> result = levelOrderTraversal(root);
        for (String level : result) {
            System.out.println(level);
        }
        sc.close();
    }
}

C++ 代码

#include <iostream>
#include <sstream>
#include <queue>
#include <vector>
using namespace std;

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

// 根据层次遍历结果构造二叉树
TreeNode* buildTree(const vector<string>& level_order) {
    if (level_order.empty() || level_order[0] == "null")
        return nullptr;
    
    TreeNode* root = new TreeNode(stoi(level_order[0]));
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while (i < level_order.size()) {
        TreeNode* current = q.front();
        q.pop();
        // 构造左子节点
        if (i < level_order.size() && level_order[i] != "null") {
            current->left = new TreeNode(stoi(level_order[i]));
            q.push(current->left);
        }
        i++;
        // 构造右子节点
        if (i < level_order.size() && level_order[i] != "null") {
            current->right = new TreeNode(stoi(level_order[i]));
            q.push(current->right);
        }
        i++;
    }
    return root;
}

// 层次遍历二叉树，并打印每层结果
void levelOrderTraversal(TreeNode* root) {
    if (root == nullptr)
        return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int levelSize = q.size();
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front();
            q.pop();
            cout << node->val;
            if (i < levelSize - 1) {
                cout << " ";
            }
            if (node->left) {
                q.push(node->left);
            }
            if (node->right) {
                q.push(node->right);
            }
        }
        cout << endl;
    }
}

int main() {
    string input;
    getline(cin, input);
    // 用字符串流处理输入，以空格分隔各个节点
    istringstream iss(input);
    vector<string> nodes;
    string val;
    while (iss >> val) {
        nodes.push_back(val);
    }
    // 构造二叉树
    TreeNode* root = buildTree(nodes);
    // 层次遍历并输出结果
    levelOrderTraversal(root);
    return 0;
}

Leetcode 41.二叉树的层次遍历-原题链接

题目内容

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

输入描述

一行包含二叉树的序列化数组，节点值之间用空格隔开，空节点用null表示。

输出描述

从$root_0$开始层序遍历，每层一行输出，一行里的数字之间以空格分隔。（不输出空节点）

样例1

输入

3 9 20 null null 15 7

输出

3
9 20
15 7

样例2

输入

1

输出

1

提示

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