哎， 晒个风景吧~
走在食堂的路上
今天的天空，白云朵朵。。。祝今天去INTERSPEECH 2016的小伙伴，一切顺利！
每天生活的地方
时间限制：1秒空间限制：32768K
题目描述
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
我看网上大部分的算法是利用栈，两个栈之间来回颠倒，这个思想也是很好的。
上代码！
/*1. 首先将根节点压入栈s1。
2. 将s1依次出栈，保存每个节点值，并依次将每个节点的左右节点压入栈s2
3. 将s2依次出栈，保存每个节点值，并依次将每个节点的右左节点压入本s1<注：这里是先压右子节点再压左子节点>
*/
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int> > result;
if (!pRoot) { return result; }
stack<TreeNode*> s1;
stack<TreeNode*> s2;
vector<int> temp;
s1.push(pRoot);
while (true) {
while (!s1.empty()) {
TreeNode* ptr = s1.top();
s1.pop();
if (!ptr) { continue; }
s2.push(ptr->left);
s2.push(ptr->right);
temp.push_back(ptr->val);
}
if (temp.empty()) { break; }
result.push_back(temp);
temp.clear();
/* 如果先把val记录下来则需要判断，那么在以后放入节点的时候要判别是否为空，否则需要先判别为空，然后保存值。*/
while (!s2.empty()) {
TreeNode* ptr = s2.top();
s2.pop();
if (!ptr) { continue; }
s1.push(ptr->right);
s1.push(ptr->left);
temp.push_back(ptr->val);
}
if (temp.empty()) { break; }
result.push_back(temp);
temp.clear();
}
return result;
}
};
以上代码来自网络，顺便说一句TreeNode* ptr用过之后还有要释放掉的吧！！！
ptr=NULL; //先设置为NULL
free(ptr);//释放内存 （所有自己申请的空间记得释放哟！）
我的解法，利用一个双端队列也可以达到效果哟！
Paste_Image.png
/*
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> > vec;
if(pRoot==NULL) return vec;
//创建队列
deque<TreeNode*> q;
q.push_back(pRoot);
int left=0;
int numberOfChildren=1;
TreeNode* tempNode=NULL;
while(!q.empty())
{
vector<int> temp;
//进入队列
for(int i=0; i<numberOfChildren; ++i)
{
if(left%2==0) //左 到 右 右出左进 左孩子先
{
tempNode = q.back();
q.pop_back();
//保存打印顺序
temp.push_back(tempNode->val);
//孩子入队列
if(tempNode->left!=NULL)
{
q.push_front(tempNode->left);
}
if(tempNode->right!=NULL)
{
q.push_front(tempNode->right);
}
}
else //右 到 左 左出右进 右孩子先
{
tempNode = q.front();
q.pop_front();
//保存打印顺序
temp.push_back(tempNode->val);
//孩子入队列
if(tempNode->right!=NULL)
{
q.push_back(tempNode->right);
}
if(tempNode->left!=NULL)
{
q.push_back(tempNode->left);
}
}
}
vec.push_back(temp);
left++;
numberOfChildren=q.size();
}
//free(tempNode); 释放内存居然，内存空间还变大，不明觉厉。但是还是应该释放的。
return vec;
}
};
