题解 | #把二叉树打印成多行#

初次版本：分层的层次遍历，常规层次遍历用一个队列，无法确定遍历节点的层次，可以考虑用两个队列分别存储奇偶层的节点，交替存储和遍历；

class Solution {
public:
        vector<vector<int> > Print(TreeNode* pRoot) {
            vector<vector<int>> res;
            queue<TreeNode*> l ,r;
            int count = 1;
            if(!pRoot)
                return res;
            l.push(pRoot);
            while(!l.empty() || !r.empty()){
                TreeNode* temp;
                vector<int> v;
                if(count % 2){
                    while(!l.empty()){
                        temp = l.front();
                        v.push_back(temp->val);
                        l.pop();
                        if(temp->left)
                            r.push(temp->left);
                        if(temp->right)
                            r.push(temp->right);
                    }
                }
                else{
                    while(!r.empty()){
                        temp = r.front();
                        v.push_back(temp->val);
                        r.pop();
                        if(temp->left)
                            l.push(temp->left);
                        if(temp->right)
                            l.push(temp->right);
                    }
                }
                res.push_back(v);
                count ++;
            }
            return res;
        }
    
};

改进：可以直接用当前队列的大小控制层次：

class Solution {
public:
        vector<vector<int> > Print(TreeNode* pRoot) {
            vector<vector<int>> res;
            queue<TreeNode*> q;
            int depth = 1;
            if(!pRoot)
                return res;
            q.push(pRoot);
            while(!q.empty()){
                int size = q.size();
                vector<int> v;
                TreeNode* temp;
                while(size --){
                    temp = q.front();
                    v.push_back(temp->val);
                    q.pop();
                    if(temp->left)
                        q.push(temp->left);
                    if(temp->right)
                        q.push(temp->right);
                }
                res.push_back(v);
            }
            return res;
        }
    
};

递归做法：考虑递归遍历，通过参数depth去维护当前节点所在层次，如果是首次遍历该层次，则创建新的数组，否则直接push到对应层次的数组，再分别遍历左右子节点。

class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int>> res;
        int depth = 1;
        if(!pRoot)
            return res;
        print(pRoot, depth, res);
        return res;
    }
    
    void print(TreeNode* root, int depth, vector<vector<int>> &res){
        if(depth > res.size()){
            vector<int> v;
            v.push_back(root->val);
            res.push_back(v);
        }
        else{
            res[depth - 1].push_back(root->val);
        }
        if(root->left)
            print(root->left, depth + 1, res);
        if(root->right)
            print(root->right, depth + 1, res);
    }
    
    
};