题目很简单,打印二叉数每一层的内容
如果要用到递归的方法需要想一下才能想明白
因为递归比较难解释,我只能尽量解释
思路:
首先我们需要一个递归的函数,因为我们对这个数组进行操作,所以按引用传入数组
还需要接收当前地址cur和深度depth
这个比深度优先的代码多了一个深度,因为递归按照顺序递归下去的话,会到二叉树的叶子部分,但是我们不需要直接就加入叶子部分。所以需要用一个代表深度的变量来表示深度。对应的深度加入对应的值。
看递归结构把。终止条件是:cur为nullptr 此时直接return
因为有一个深度,我们需要在数组的size对于深度时,往二维数组中再加一行
然后往depth中加入一个cur指向的数值
最后两个递归
看代码
# 递归法
class Solution {
public:
void order(TreeNode* cur, vector<vector<int>>& result, int depth)
{
if (cur == nullptr) return;
if (result.size() == depth) result.push_back(vector<int>());
result[depth].push_back(cur->val);
order(cur->left, result, depth + 1);
order(cur->right, result, depth + 1);
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
int depth = 0;
order(root, result, depth);
return result;
}
};