按之字形顺序打印二叉树

• 时间限制：1秒空间限制：32768K
• 通过比例：30.04%
• 最佳记录：0 ms|8552
  

题目描述

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

/*
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> > ret;
        if(!pRoot) return ret;
        vector<int> curLayer;
        vector<TreeNode*> LevelSearch;
        TreeNode *cur=pRoot;
        LevelSearch.push_back(cur);
        int start=0,end=0;
        bool LR=false;
        do{
            for(int i=start;i<=end;++i){
                if(LevelSearch[i]->left) LevelSearch.push_back(LevelSearch[i]->left);
                if(LevelSearch[i]->right) LevelSearch.push_back(LevelSearch[i]->right);
                curLayer.push_back(LevelSearch[i]->val);
            }
            if(LR){
                int temp=-1;
                for(int i=0,j=curLayer.size()-1;i<j;++i,--j){
                    temp=curLayer[i];
                    curLayer[i]=curLayer[j];
                    curLayer[j]=temp;
                }
            }
            ret.push_back(curLayer);
            LR=!LR;
            curLayer.clear();
            start=end+1;
            end=LevelSearch.size()-1;
        }while(start<=end);

        return ret;
    }
};