题目描述
算法1
BFS $O(n)$
这里有一个值得注意的点是,当我们开始访问某一层的第一个节点时,此时队列中的节点总数即为这一层的节点数目
C++ 代码
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
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 == NULL){
return res;
}
queue<TreeNode*> q;
q.push(root);
TreeNode* cur; // 代表当前取出的节点
while (!q.empty()){
vector <int> row; //记录二叉树的一行
int n = q.size(); // 记录当前行有多少节点,也就是下面的for循环我们可以连着取出多少
for(int i = 0; i < n; i++){
cur = q.front();
q.pop();
row.push_back(cur -> val);
// 若是左右孩子存在,则将左右孩子加入下一层次
if (cur -> left)
q.push(cur->left);
if (cur -> right)
q.push(cur->right);
}
res.push_back(row);
}
return res;
}
};
算法2
递归 $O(n)$
按行遍历的关键是每一行的深度对应了它输出在二维数组中的深度,即深度可以与二维数组的下标对应,那我们可以在递归的访问每个节点的时候记录深度。
void traverse(TreeNode root, int depth)
进入子节点则深度加1:
//递归左右时深度记得加1
traverse(root.left, depth + 1);
traverse(root.right, depth + 1);
每个节点值放入二维数组相应行。
res[depth - 1].push_back(root->val);
step 1:首先判断二叉树是否为空,空树没有遍历结果。
step 2:使用递归进行层次遍历输出,每次递归记录当前二叉树的深度,每当遍历到一个节点,如果为空直接返回。
step 3:如果遍历的节点不为空,输出二维数组中一维数组的个数(即代表了输出的行数)小于深度,说明这个节点应该是新的一层,我们在二维数组中增加一个一维数组,然后再加入二叉树元素。
step 4:如果不是step 3的情况说明这个深度我们已经有了数组,直接根据深度作为下标取出数组,将元素加在最后就可以了。
step 5:处理完这个节点,再依次递归进入左右节点,同时深度增加。因为我们进入递归的时候是先左后右,那么遍历的时候也是先左后右,正好是层次遍历的顺序。
C++ 代码
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型vector<vector<>>
*/
void traverse(TreeNode* root, vector<vector<int>>& res, int depth){
if (root){ // 如果此时还有节点,则递归为其层次遍历
if(res.size() < depth){ // 如果是第一次访问此深度的节点,则需要在res列表中添加代表此深度的数组
res.push_back(vector<int>{});
}
res[depth - 1].push_back(root -> val);
}
else {
return;
}
// 递归进入下一层
traverse(root->left, res, depth + 1);
traverse(root -> right, res, depth + 1);
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
int depth = 1;
if(root == NULL){
return res;
}
traverse(root, res, depth);
return res;
}
};