二叉树的最大深度和二叉树的层次遍历 II

做了这个之后的感想，大概是两点，虽然说这两点都是常识吧：第一是在和树相关的题目上，递归不是万能的，像层次遍历levelOrder这种的还得用辅助队列迭代；第二是在递归的过程中可以用参数来保存状态。

树的最大深度这个问题，我看官方题解（包括算法书上）给出的是那种语义化的解法，也就是这种：

int maxDepth(TreeNode *root) { if (root == nullptr) { return 0; } int left_max = maxDepth(root->left); int right_max = maxDepth(root->right); return std::max(left_max, right_max) + 1; }

这种解法的语义很好，但我感觉占的空间会比较大，因为每一步都需要保存一个返回值，所以我就用参数来传状态了：

int max = 0; void countDepth(TreeNode *root, int depth) { if (root == nullptr) { if (depth > max) { max = depth; } return; } ++depth; countDepth(root->left, depth); countDepth(root->right, depth); } int maxDepth(TreeNode *root) { countDepth(root, 0) return max; }

至于层次遍历，一般来说层次遍历似乎是不得不用辅助队列进行迭代的。所以索性就用迭代做了：

vector<vector<int>> levelOrderBottom(TreeNode *root) { vector<vector<int>> result; if (root == nullptr) { return result; } result.push_back({root->val}); queue<TreeNode *> record; record.push(root); while (!record.empty()) { vector<int> vec; queue<TreeNode *> temp; while (!record.empty()) { root = record.front(); if (root->left) { vec.push_back(root->left->val); temp.push(root->left); } if (root->right) { vec.push_back(root->right->val); temp.push(root->right); } record.pop(); } if (vec.size()) { result.push_back(vec); } while (!temp.empty()) { record.push(temp.front()); temp.pop(); } } reverse(result.begin(), result.end()); return result; }

可以感觉到这个代码是非常丑陋了。其实思路很简单，就是每一层提前处理下一层，把下一层的内容放进去。因为题目要求最后还得倒序，所以还多了一个翻转的过程；每一步还得用另一个辅助队列去存下一层的内容。

后来看到一个递归的解法，虽然说也是差不多的思路（并且也用了很多队列，笑），但是我觉得这个解法给我提了个醒，递归还可以这样用：

void levelOrderBottom(queue<TreeNode *> que, vector<vector<int>> &ans) { if (que.empty()) return; queue<TreeNode *> queNext; vector<int> vec; while (!que.empty()) { TreeNode *pNode = que.front(); que.pop(); vec.push_back(pNode->val); if (pNode->left != nullptr) queNext.push(pNode->left); if (pNode->right != nullptr) queNext.push(pNode->right); } levelOrderBottom(queNext, ans); // 我想说的是这一句 ans.push_back(vec); } vector<vector<int>> levelOrderBottom(TreeNode* root) { vector<vector<int>> ans; queue<TreeNode *> q; if (root != nullptr) q.push(root); levelOrderBottom(q, ans); return ans; }

我现在觉得，中间件这个东西，是不是就是从递归中脱胎而出的。

另外吧，我感觉迭代相比起递归有一个特点，就是完全按照从前到后的顺序进行。这个倒不是指的下标啥的，因为可以倒序遍历，我指的是那种先到达最底层再逐层往上的能力。可能这就是子问题吧。