LeetCode 102. 【二叉树的层序遍历】
原题链接
简单
作者:
大明湖的鱼
,
2021-01-16 15:28:37
,
所有人可见
,
阅读 263
利用前序遍历实现层序遍历
- $depth$记录当前层数,进入下一层时$depth$+1
- 如果$depth > ans.size()$ ,说明$ans$还没开到第一层,要扩容
- 对于每一层push 的先后顺序,因为 NLR ,所以是合法的
/**
* 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>> ans;
pre(root,0,ans);
return ans;
}
void pre(TreeNode* root , int depth ,vector<vector<int>> &ans){
if(root == NULL) return ;
if(depth >=ans.size()) ans.emplace_back(vector<int>{});//扩容
ans[depth].emplace_back(root->val);
pre(root->left,depth+1,ans);
pre(root->right,depth+1,ans);
}
};
队列实现,关键是分开这是第几层
/**
* 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>> res;
if(root == nullptr) return res;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
vector<int> tmp;
int len = q.size();
for(int i = 0 ;i < len; i++){
TreeNode* node = q.front();
q.pop();
tmp.emplace_back(node->val);
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
res.emplace_back(tmp);
}
return res;
}
};