题目描述补充

题目： 实现二叉树的层次遍历（也称为广度优先遍历）。给定一个二叉树，按照从上到下、从左到右的顺序遍历二叉树的节点，并返回遍历的结果。

示例：

给定二叉树：

    3
   / \
  9  20
    /  \
   15   7

应该返回遍历的结果为：[3, 9, 20, 15, 7]。

示例代码

PHP 示例

<?php

class TreeNode {
    public $val;
    public $left;
    public $right;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

function levelOrder($root) {
    if ($root === null) {
        return [];
    }
    
    $result = [];
    $queue = new SplQueue();
    $queue->enqueue($root);
    
    while (!$queue->isEmpty()) {
        $levelSize = $queue->count();
        $levelNodes = [];
        
        for ($i = 0; $i < $levelSize; $i++) {
            $node = $queue->dequeue();
            $levelNodes[] = $node->val;
            
            if ($node->left !== null) {
                $queue->enqueue($node->left);
            }
            if ($node->right !== null) {
                $queue->enqueue($node->right);
            }
        }
        
        $result[] = $levelNodes;
    }
    
    // 如果题目要求的是一维数组而非二维（每层作为子数组），则进行合并
    return array_merge(...$result);
}

// 示例用法
$root = new TreeNode(3);
$root->left = new TreeNode(9);
$root->right = new TreeNode(20);
$root->right->left = new TreeNode(15);
$root->right->right = new TreeNode(7);

print_r(levelOrder($root));
?>

Python 示例

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 levelOrder(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        level_nodes = []
        
        for _ in range(level_size):
            node = queue.popleft()
            level_nodes.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.extend(level_nodes)  # 如果需要一维数组
        # 如果需要二维数组，则取消上一行，并取消注释下一行
        # result.append(level_nodes)
    
    return result

# 示例用法
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print(levelOrder(root))

JavaScript 示例

class TreeNode {
    constructor(val, left, right) {
        this.val = (val===undefined ? 0 : val)
        this.left = (left===undefined ? null : left)
        this.right = (right===undefined ? null : right)
    }
}

function levelOrder(root) {
    if (!root) return [];
    
    const result = [];
    const queue = [root];
    
    while (queue.length > 0) {
        const levelSize = queue.length;
        const levelNodes = [];
        
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift();
            levelNodes.push(node.val);
            
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        
        result.push(...levelNodes); // 如果需要一维数组
        // 如果需要二维数组，则改为 result.push(levelNodes);
    }
    
    return result;
}

// 示例用法
const root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);

console.log(levelOrder(root));

码小课网站中有更多相关内容分享给大家学习，包括但不限于算法题解、数据结构深入讲解等，欢迎大家访问学习。