叹隙中驹
石中火
梦中身
C++，层序遍历。
其实主要就是把层序遍历的层数记住，至于怎么记住有很多种方法，我这里用的是内层循环每次把一层全部压入vector实现的。其实我还写过前序递归的，思路也是类似的，也更简单，具体可以参考leetcode102。
非递归的如下：
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
vector<vector<int>> Print(TreeNode* pRoot) {
vector<vector<int>> ans;
if (!pRoot) return ans;
queue<TreeNode *> q;
q.push(pRoot);
while (!q.empty()) {
vector<int> tempv;
int cnt = q.size();
while (cnt) {
TreeNode *temp = q.front();
q.pop();
tempv.push_back(temp->val);
if (temp->left)
q.push(temp->left);
if (temp->right)
q.push(temp->right);
cnt--;
}
ans.push_back(tempv);
}
for (int i = 0; i < ans.size(); i++) {
if (i % 2 != 0)
reverse(ans[i].begin(), ans[i].end());
}
return ans;
}
};
递归版本如下：
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
pre(root, 0, ans);
for (int i = 0; i < ans.size(); i++) {
if (i % 2 != 0)
reverse(ans[i].begin(), ans[i].end());
}
return ans;
}
void pre(TreeNode *root, int depth, vector<vector<int>> &ans) {
if (!root) return ;
if (depth >= ans.size())
ans.push_back(vector<int> {});
ans[depth].push_back(root->val);
pre(root->left, depth + 1, ans);
pre(root->right, depth + 1, ans);
}
};
显然递归的更简单哈哈哈！
