[剑指offfer] 从上到下打印二叉树 II (C++解法)
程序员文章站
2022-07-14 18:04:59
...
从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果:
[
[3],
[9,20],
[15,7]
]
提示:
节点总数 <= 1000
C++解法
思路:使用队列层次遍历访问二叉树,每一层输出的元素个数刚好为队列当前的size()。
/**
* 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:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> vv;
if (!root)
return vv;
vector<int> v;
queue<TreeNode*> q;
TreeNode* node;
q.push(root);
while (!q.empty()) {
int levelSize = q.size();
for (int i = 0; i < levelSize; ++i) {
node = q.front();
v.push_back(node->val);
q.pop();
if (node->left != NULL)
q.push(node->left);
if (node->right != NULL)
q.push(node->right);
}
vv.push_back(v);
v.clear();
}
return vv;
}
};