哎危虱， 曬個(gè)風(fēng)景吧~

走在食堂的路上

今天的天空，白云朵朵唐全。埃跷。。祝今天去INTERSPEECH 2016的小伙伴邮利，一切順利弥雹！

每天生活的地方

時(shí)間限制：1秒空間限制：32768K
題目描述

請實(shí)現(xiàn)一個(gè)函數(shù)按照之字形打印二叉樹，即第一行按照從左到右的順序打印延届，第二層按照從右至左的順序打印剪勿，第三行按照從左到右的順序打印，其他行以此類推方庭。

我看網(wǎng)上大部分的算法是利用棧厕吉，兩個(gè)棧之間來回顛倒，這個(gè)思想也是很好的械念。

上代碼头朱！

/*1. 首先將根節(jié)點(diǎn)壓入棧s1。
   2. 將s1依次出棧龄减，保存每個(gè)節(jié)點(diǎn)值项钮，并依次將每個(gè)節(jié)點(diǎn)的左右節(jié)點(diǎn)壓入棧s2
   3. 將s2依次出棧，保存每個(gè)節(jié)點(diǎn)值，并依次將每個(gè)節(jié)點(diǎn)的右左節(jié)點(diǎn)壓入本s1<注：這里是先壓右子節(jié)點(diǎn)再壓左子節(jié)點(diǎn)>
*/
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記錄下來則需要判斷烁巫，那么在以后放入節(jié)點(diǎn)的時(shí)候要判別是否為空署隘，否則需要先判別為空，然后保存值亚隙。*/
            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;
    }
};

以上代碼來自網(wǎng)絡(luò)磁餐，順便說一句TreeNode* ptr用過之后還有要釋放掉的吧！Ｊ研崖媚！

ptr=NULL; //先設(shè)置為NULL
free(ptr);//釋放內(nèi)存  （所有自己申請的空間記得釋放喲！）

我的解法恤浪，利用一個(gè)雙端隊(duì)列也可以達(dá)到效果喲畅哑！

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;
        //創(chuàng)建隊(duì)列
        deque<TreeNode*> q;
        q.push_back(pRoot);
        int left=0;
        int numberOfChildren=1;
        TreeNode* tempNode=NULL;
        while(!q.empty())
        {
            vector<int> temp;
            //進(jìn)入隊(duì)列
            for(int i=0; i<numberOfChildren; ++i)
            {
                if(left%2==0) //左 到 右   右出左進(jìn)   左孩子先
                {
                    tempNode = q.back();
                    q.pop_back();
                    //保存打印順序
                    temp.push_back(tempNode->val);
                    //孩子入隊(duì)列
                    if(tempNode->left!=NULL)
                    {
                        q.push_front(tempNode->left);
                    }
                    if(tempNode->right!=NULL)
                    {
                        q.push_front(tempNode->right);
                    }
                }
                else  //右 到 左   左出右進(jìn)   右孩子先
                {
                    tempNode = q.front();
                    q.pop_front();
                    //保存打印順序
                    temp.push_back(tempNode->val);
                    //孩子入隊(duì)列
                    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);  釋放內(nèi)存居然，內(nèi)存空間還變大水由，不明覺厲荠呐。但是還是應(yīng)該釋放的。
        return vec;
    }
};