从上往下打印二叉树这个是不分行的，用一个队列就可以实现
class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int> result;
queue<TreeNode* > container;
if(root == NULL)
return result;
container.push(root);
while(container.size() != ){
TreeNode* rot = container.front();
container.pop();
if(rot->left != NULL)
container.push(rot->left);
if(rot->right != NULL)
container.push(rot->right);
result.push_back(rot->val);
}
return result;
}
};
leetcode102题是分行打印的，相对于直接从上往下打印，需要把每行表示出来。同样利用队列，但是需增加两个变量来统计分行的信息。
注意一个细节:if(node->left != NULL) 与 if(!node->left) 不一样，即if(!node->left)中感叹号！的优先级高于->left
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
if(!root)
return result;
vector<int> res;
queue<TreeNode*> container;
container.push(root);
int now = ;
int next = ;
while(!container.empty()){
TreeNode* node = container.front();
container.pop();
res.push_back(node->val);
now--;
if(node->left != NULL){
container.push(node->left);
next++;
}
if(node->right != NULL){
container.push(node->right);
next++;
}
if(now == ){
now = next;
next = ;
result.push_back(res);
res.clear();
}
}
return result;
}
};
打印多行的另一种写法，个人觉得这种写法比较简洁，少两个变量
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
if(root == NULL)
return result;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
vector<int> res;
for(int i = q.size();i > ;i--){
TreeNode* node = q.front();
q.pop();
res.push_back(node->val);
if(node->left)
q.push(node->left);
if(node->right)
q.push(node->right);
}
result.push_back(res);
}
return result;
}
};
leetcode107与102差不多，都是按行打印，但是107是从底层打印到高层。实际代码中，依旧是正常打印，只是在最后输出时用insert进行逆序就好了
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> result;
if(root == NULL)
return result;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
vector<int> res;
for(int i = q.size();i > ;i--){
TreeNode* node = q.front();
res.push_back(node->val);
q.pop();
if(node->left)
q.push(node->left);
if(node->right)
q.push(node->right);
}
result.insert(result.begin(),res);
}
return result;
}
};
在102和107中，自己都写了一种错误写法，比如102的错误写法如下：
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> result;
if(root == NULL)
return result;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
vector<int> res;
for(int i = ;i < q.size();i++){
TreeNode* node = q.front();
res.push_back(node->val);
q.pop();
if(node->left)
q.push(node->left);
if(node->right)
q.push(node->right);
}
result.insert(result.begin(),res);
}
return result;
}
};
错误如下：
输入是：[3,9,20,null,null,15,7]
正确输出是：[[3],[9,20],[15,7]]
实际的错误输出是：[[3,9],[20,15],[7]]
主要错误是在for循环当中，for循环的截止条件是<q.size()，这个q的size在每次循环中是变化的，但是实际上我只想要初始的size，这个size表达的是同一层有多少个的节点
注意：for循环中，初始化是只是第一次计算，但是循环判断条件，每次循环都要重新计算
这也是bug的原因所在
103. Binary Tree Zigzag Level Order Traversal(剑指offer之字型打印)
注意：第一行先放左后放右，第二行是先放右后放左。用两个堆进行实现。
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> result;
vector<int> res;
if(root == NULL)
return result;
stack<TreeNode*> sta1;
stack<TreeNode*> sta2;
sta1.push(root);
int next = ;
while(!sta1.empty() || !sta2.empty()){
if(next % == ){
TreeNode* node = sta1.top();
res.push_back(node->val);
sta1.pop();
if(node->left)
sta2.push(node->left);
if(node->right)
sta2.push(node->right);
if(sta1.empty()){
next++;
result.push_back(res);
res.clear();
}
}
else{
TreeNode* node = sta2.top();
res.push_back(node->val);
sta2.pop();
if(node->right)
sta1.push(node->right);
if(node->left)
sta1.push(node->left);
if(sta2.empty()){
next++;
result.push_back(res);
res.clear();
}
}
}
return result;
}
};