题目描述
题目链接:102. Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
例子
例子 1
Input: [3,9,20,null,null,15,7] Output: [ [3], [9,20], [15,7] ]
解题思路
这道题要求我们层序遍历输出二叉树,并且要求层与层之间用不同 vector
存储。如果不要求区分层次我们只需要用一个 queue
来通过广度优先搜索实现即可,方法是:
- 先将根节点推入,然后进行循环
- 每次从队列中取出一个节点,将它的值压入结果
vector
中 - 并将其左右节点(如果存在)推入队列中
- 循环直至队列为空为止即可。
现在要求层次之间要区分,我们可以用两个 queue
来实现,q1
用来存储当前遍历的层次的节点,q2
用来存储下一个层次的节点。方法是:
- 先将根节点推入
q1
,然后进行循环 - 初始化一个
vector
存储当前层的值,v
- 初始化一个
queue
存储下一层节点,q2
- 循环遍历
q1
- 从
q1
中取出一个节点,将它的值推入v
中 - 将其左右节点(如果存在)推入
q2
q1
遍历完后,将q2
赋值给q1
进行下一次循环- 循环直至
q1
为空即可
代码如下:
#include <algorithm>
#include <queue>
#include <vector>
class Solution {
public:
std::vector<std::vector<int>> levelOrder(TreeNode* root) {
std::vector<std::vector<int>> result;
if (!root) return result;
std::queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
std::queue<TreeNode*> new_q;
std::vector<int> level;
while (!q.empty()) {
TreeNode* curr = q.front();
q.pop();
if (curr->left) new_q.push(curr->left);
if (curr->right) new_q.push(curr->right);
level.push_back(curr->val);
}
result.push_back(level);
std::swap(new_q, q);
}
return result;
}
};
- 时间复杂度: O(n)
- 空间复杂度: O(w)
GitHub 代码同步地址: 102.BinaryTreeLevelOrderTraversal.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions