算法进阶——求二叉树的层序遍历
2023-12-28 15:33:54
题目
给定一个二叉树,返回该二叉树层序遍历的结果,(从左到右,一层一层地遍历)。
例如:
给定的二叉树是{3,9,20,#,#,15,7},
该二叉树层序遍历的结果是
[
[3],
[9,20],
[15,7]
]
提示:
0 <= 二叉树的结点数 <= 1500
示例1
输入:
{1,2}
返回值:
[[1],[2]]
示例2
输入:
{1,2,3,4,#,#,5}
返回值:
[[1],[2,3],[4,5]]
思路
利用辅助队列,通过bfs(广度优先)算法遍历二叉树,按层次顺序记录节点。
我的解答代码还有一个可以优化的点是,每层的节点数其实就是当前辅助队列的大小,这样其实不需要next_level_num和to_be_handle这2个辅助变量。
解答代码
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
#include <queue>
class Solution {
public:
/**
* @param root TreeNode类
* @return int整型vector<vector<>>
*/
vector<vector<int> > levelOrder(TreeNode* root) {
// write code here
vector<vector<int> > res;
if (root == nullptr) {
return res;
}
// bfs
queue<TreeNode*> nodes;
nodes.push(root);
int next_level_num = 0;// 下一层的节点数
int to_be_handle = 1;// 本层还未处理的节点数
vector<int> cur;// 本层的遍历结果
while (!nodes.empty()) {
auto node = nodes.front();
if (node->left != nullptr) {
nodes.push(node->left);
++next_level_num;
}
if (node->right != nullptr) {
nodes.push(node->right);
++next_level_num;
}
cur.push_back(node->val);
nodes.pop();
--to_be_handle;
if (to_be_handle == 0) {
// 本层处理完了
res.push_back(cur);
cur.clear();
to_be_handle = next_level_num;
next_level_num = 0;
}
}
return res;
}
};
文章来源:https://blog.csdn.net/caesar1228/article/details/135269670
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!