赞
踩
给你二叉树的根节点 root ,返回其节点值的 层序遍历。(即逐层地,从左到右访问所有节点)。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]
示例 2:
输入:root = [1]
输出:[[1]]
示例 3:
输入:root = []
输出:[]
队列是一种先进先出(FIFO)的数据结构,非常适合于层序遍历,因为我们总是希望按照从树的上层到下层的顺序处理节点。
1、初始化阶段
2、遍历阶段
队列操作:使用一个队列来管理待处理的树节点。队列的先进先出特性保证了树的每一层都按照从左到右的顺序被处理。
层级处理:
节点处理:
存储层次数据:
3、结束阶段
4、总体来看
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) { // 接受一个 TreeNode* 类型的参数,返回一个 vector<vector<int>> 类型的二维向量。
queue<TreeNode*> que; // 用于按层序存储树中的节点,以便按顺序访问
if(root != NULL) que.push(root);
vector<vector<int>> result;
while(!que.empty()){
int size = que.size();
vector<int> vec;
for(int i = 0; i < size; i++){
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
}
result.push_back(vec);
}
return result;
}
};
int main() {
// 创建特定的二叉树:[3,9,20,null,null,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;
vector<vector<int>> result = solution.levelOrder(root);
for (const vector<int>& level : result) {
for (int val : level) {
cout << val << " ";
}
cout << endl;
}
return 0;
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。