二叉树的层序遍历
题目要求
设计一个算法，实现对一棵二叉树进行层序遍历。层序遍历是指按照从上到下、从左到右的顺序访问树中的每个节点。具体来说，就是先访问根节点，然后访问第二层的所有节点，接着是第三层的所有节点，以此类推，直到访问到最后一层的所有节点。
输入：一棵二叉树的根节点 root。 输出：一个列表，其中包含二叉树的层序遍历结果。
解题思路
层序遍历通常使用队列这一数据结构来实现。以下是解题的步骤：
- 初始化一个队列，将根节点入队。
- 当队列不为空时，进行以下操作： a. 记录当前队列的长度，这个长度表示当前层的节点数。 b. 循环遍历当前层的节点，对于每个节点，执行以下操作： i. 将节点的值加入到当前层的结果列表中。 ii. 如果该节点有左子节点，则将左子节点入队。 iii. 如果该节点有右子节点，则将右子节点入队。 c. 当前层遍历完成后，将当前层的结果列表加入到最终的层序遍历结果列表中。
- 当队列为空时，所有层的节点都已访问完毕，返回最终的层序遍历结果列表。
这种方法确保了每次只处理一层的节点，并且通过队列先进先出的特性来保证左右子节点的访问顺序。
Golang 版本
package main
import (
"fmt"
)
// TreeNode is a structure for tree nodes
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// levelOrder performs a level-order traversal on a binary tree
func levelOrder(root *TreeNode) [][]int {
result := [][]int{}
if root == nil {
return result
}
queue := []*TreeNode{root}
for len(queue) > 0 {
level := []int{}
levelLength := len(queue)
for i := 0; i < levelLength; i++ {
node := queue[0]
queue = queue[1:]
level = append(level, node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
result = append(result, level)
}
return result
}
func main() {
// Example usage:
// Construct a binary tree as an example
// 3
// / \
// 9 20
// / \
// 15 7
root := &TreeNode{3, &TreeNode{9, nil, nil}, &TreeNode{20, &TreeNode{15, nil, nil}, &TreeNode{7, nil, nil}}}
fmt.Println(levelOrder(root))
}
这段代码定义了一个TreeNode结构体，用于表示二叉树的节点，并实现了levelOrder函数来进行层序遍历。main函数中给出了一个使用示例，构造了一棵简单的二叉树，并打印了其层序遍历的结果。
C++版本
#include <iostream>
#include <vector>
#include <queue>
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
std::vector<std::vector<int>> levelOrder(TreeNode* root) {
std::vector<std::vector<int>> result;
if (!root) return result;
std::queue<TreeNode*> nodesQueue;
nodesQueue.push(root);
while (!nodesQueue.empty()) {
int levelSize = nodesQueue.size();
std::vector<int> currentLevel;
for (int i = 0; i < levelSize; ++i) {
TreeNode* node = nodesQueue.front();
nodesQueue.pop();
currentLevel.push_back(node->val);
if (node->left) nodesQueue.push(node->left);
if (node->right) nodesQueue.push(node->right);
}
result.push_back(currentLevel);
}
return result;
}
};
int main() {
// Example usage:
// Construct a binary tree as an example
// 3
// / \
// 9 20
// / \
// 15 7
TreeNode *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);
Solution solution;
std::vector<std::vector<int>> result = solution.levelOrder(root);
// Print the level order traversal
for (const auto& level : result) {
for (int val : level) {
std::cout << val << " ";
}
std::cout << std::endl;
}
// Clean up the allocated nodes
delete root->right->right;
delete root->right->left;
delete root->right;
delete root->left;
delete root;
return 0;
}
这段 C++代码定义了一个TreeNode结构体，用于表示二叉树的节点，并实现了一个Solution类，其中包含了levelOrder函数来进行层序遍历。main函数中给出了一个使用示例，构造了一棵简单的二叉树，并打印了其层序遍历的结果。最后，代码中还包含了适当的内存清理操作，以删除分配的节点。
Python 版本
from collections import deque
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def levelOrder(self, root: TreeNode) -> [[int]]:
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
level = []
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
# Example usage:
if __name__ == "__main__":
# Construct a binary tree as an example
# 3
# / \
# 9 20
# / \
# 15 7
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
solution = Solution()
print(solution.levelOrder(root))
这段 Python 代码定义了一个TreeNode类，用于表示二叉树的节点，并实现了一个Solution类，其中包含了levelOrder方法来进行层序遍历。在__main__部分中，给出了一个使用示例，构造了一棵简单的二叉树，并打印了其层序遍历的结果。
Java 版本
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List<Integer> currentLevel = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
currentLevel.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.add(currentLevel);
}
return result;
}
}
// Example usage
class Main {
public static void main(String[] args) {
// Construct a binary tree as an example
// 3
// / \
// 9 20
// / \
// 15 7
TreeNode 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);
Solution solution = new Solution();
List<List<Integer>> result = solution.levelOrder(root);
// Print the level order traversal
for (List<Integer> level : result) {
for (int val : level) {
System.out.print(val + " ");
}
System.out.println();
}
}
}
这段 Java 代码定义了一个TreeNode类，用于表示二叉树的节点，并实现了一个Solution类，其中包含了levelOrder方法来进行层序遍历。在Main类的main方法中，给出了一个使用示例，构造了一棵简单的二叉树，并打印了其层序遍历的结果。
Rust 版本
use std::cell::RefCell; use std::rc::Rc; use std::collections::VecDeque; // Definition for a binary tree node. #[derive(Debug, PartialEq, Eq)] pub struct TreeNode { pub val: i32, pub left: Option<Rc<RefCell<TreeNode>>>, pub right: Option<Rc<RefCell<TreeNode>>>, } impl TreeNode { #[inline] pub fn new(val: i32) -> Self { TreeNode { val, left: None, right: None, } } } struct Solution; impl Solution { pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> { let mut result = Vec::new(); if root.is_none() { return result; } let mut queue = VecDeque::new(); queue.push_back(root); while let Some(node) = queue.pop_front() { let mut current_level = Vec::new(); let mut next_level = VecDeque::new(); for node in queue.iter() { if let Some(node) = node { let node = node.borrow(); current_level.push(node.val); if node.left.is_some() { next_level.push_back(node.left.clone()); } if node.right.is_some() { next_level.push_back(node.right.clone()); } } } result.push(current_level); queue = next_level; } result } } fn main() { let root = Some(Rc::new(RefCell::new(TreeNode::new(3)))); let left = Some(Rc::new(RefCell::new(TreeNode::new(9)))); let right = Some(Rc::new(RefCell::new(TreeNode::new(20)))); let left_leaf = Some(Rc::new(RefCell::new(TreeNode::new(15)))); let right_leaf = Some(Rc::new(RefCell::new(TreeNode::new(7)))); if let Some(ref root_node) = root { root_node.borrow_mut().left = left; root_node.borrow_mut().right = right; if let Some(ref right_node) = root_node.borrow().right { right_node.borrow_mut().left = left_leaf; right_node.borrow_mut().right = right_leaf; } } let result = Solution::level_order(root); for level in result { for val in level { print!("{} ", val); } println!(); } }
这段 Rust 代码定义了一个TreeNode结构体，用于表示二叉树的节点，并实现了一个Solution结构体，其中包含了level_order函数来进行层序遍历。在main函数中，给出了一个使用示例，构造了一棵简单的二叉树，并打印了其层序遍历的结果。
总结
以上给出了针对二叉树进行层序遍历的解法，涵盖了多种编程语言的实现。无论是使用队列迭代的方法还是递归的方法，层序遍历都是通过逐层访问节点来实现的。这些解法都遵循了先处理当前层节点，然后将下一层节点加入队列或递归调用的基本思路。在实际应用中，可以根据具体情况选择合适的解法和编程语言来实现二叉树的层序遍历。