题解 | #按之字形顺序打印二叉树#

我的思路主要分为三个部分

1、先求出需要遍历的树的最大高度

    int Deep(TreeNode* pRoot){
        if(pRoot==nullptr) return 0;
        else return max(Deep(pRoot->left),Deep(pRoot->right))+1;
    }

已知最大高度，先把二维vector给开好

 Maxdeep=Deep(pRoot);
 for(int i=0;i<Maxdeep;i++){
 	vector<int> tmp;
 	answer.push_back(tmp);
}

2、再用前序遍历将对应层的节点加入对应层的vector之中

 void Preorder(vector<vector<int> > &answer,TreeNode* pRoot,int level){
        if(pRoot==nullptr) return;
        answer[level].push_back(pRoot->val);
        Preorder(answer,pRoot->left,level+1);
        Preorder(answer,pRoot->right,level+1);
    }

3、最后打印把偶数行翻转一下

 for(int i=0;i<answer.size();i++){
 	if(i%2==1) reverse(answer[i].begin(),answer[i].end());
 }

4、全部代码

/*
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> > answer;
    int Maxdeep;
     
    int Deep(TreeNode* pRoot){
        if(pRoot==nullptr) return 0;
        else return max(Deep(pRoot->left),Deep(pRoot->right))+1;
    }
     
    void Preorder(vector<vector<int> > &answer,TreeNode* pRoot,int level){
        if(pRoot==nullptr) return;
        answer[level].push_back(pRoot->val);
        Preorder(answer,pRoot->left,level+1);
        Preorder(answer,pRoot->right,level+1);
    }
     
    vector<vector<int> > Print(TreeNode* pRoot) {
        Maxdeep=Deep(pRoot);
        for(int i=0;i<Maxdeep;i++){
            vector<int> tmp;
            answer.push_back(tmp);
        }
        Preorder(answer,pRoot,0);
        for(int i=0;i<answer.size();i++){
            if(i%2==1) reverse(answer[i].begin(),answer[i].end());
        }
        return answer;
    }
     
};