leetcode102 二叉树的层次遍历 递归

(1) 找出重复的子问题。

层次遍历是每一层的节点从左到右的遍历，所以在遍历的时候我们可以先遍历左子树，再遍历右子树。

需要注意的是，在遍历左子树或者右子树的时候，涉及到向上或者向下遍历，为了让递归的过程中的同一层的节点放在同一个列表中，在递归时要记录深度 depth。

同时，每次遍历到一个新的 depth，结果数组中没有对应的 depth 的列表时，在结果数组中创建一个新的列表保存该 depth 的节点。

(2) 确定终止条件。

对于二叉树的遍历来说，想终止，即没东西遍历了，没东西遍历自然就停下来了。

即最下面一层的左右节点都为空了。

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;  // 存储最终结果level(root, 1, res);      // 从第1层开始递归return res;}private:void level(TreeNode* root, int depth, vector<vector<int>>& res) {if (root == nullptr) {return;  // 递归终止条件：空节点直接返回}// 如果当前深度超过结果数组大小，说明需要添加新的一层if (res.size() < depth) {res.push_back(vector<int>());}// 将当前节点值加入对应层res[depth - 1].push_back(root->val);// 递归处理左右子树，深度+1if (root->left) {level(root->left, depth + 1, res);}if (root->right) {level(root->right, depth + 1, res);}}
};

为什么需要第一句？

如果没有 res.push_back(vector<int> ());，而 num-1 已经超出了 res 的当前大小（比如 res 是空的，但 num-1 = 0），那么 res[num-1] 会访问非法内存，导致 std::out_of_range 错误。

示例：

假设 num = 1（第一层），而 res 初始为空：

• 如果没有 res.push_back(vector<int> ());，res[0] 会越界。

• 加上 res.push_back(vector<int> ()); 后，res 变成 [ [] ]，这时 res[0].push_back(val) 就能正常运行。