👌简单
从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。
这个题好像做恶很多次,上次我是用两个vector来实现的,一个放父亲,一个放子结点,然后用子节点的替换父亲的继续下一轮,但是这次我选择了队列,因为两个栈的空间复杂度有点高,这次就用队列,然后分别记住父节点和子节点的个数,然后用子结点个数替换父节点个数
#include<queue>
#include<vector>
using namespace std;
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> > res;
if (!pRoot) return res;
int num = 0;
node_queue.push(pRoot);
num++;//当前个数
while (!node_queue.empty())
{
int num_temp = 0; //子树个数
vector<int> temp_vec;
for (int i = 0; i < num; i++)
{
TreeNode* temp_node = node_queue.front();
node_queue.pop();
if (temp_node->left)
{
node_queue.push(temp_node->left);
num_temp++;
}
if (temp_node->right)
{
node_queue.push(temp_node->right);
num_temp++;
}
temp_vec.push_back(temp_node->val);
}
res.push_back(temp_vec);
num = num_temp;
}
return res;
}
private:
queue<TreeNode*> node_queue;
};