按之字形顺序打印二叉树

哎， 晒个风景吧~

走在食堂的路上

今天的天空，白云朵朵。。。祝今天去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;
    }
};