题解 | #求二叉树的层序遍历#

 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
private:
    vector<TreeNode* > cur_level_nodes_queue;
    vector<TreeNode* > next_level_nodes_queue;
    
    void traverse_curlevel(vector<TreeNode* > &cur_level, vector<TreeNode* > &next_level, vector<int> &cur_out) {
        int size = cur_level.size();
        //cout<<"cur level size:"<<size<<endl;
        for ( int i = 0; i < size; i++) {
            TreeNode* cur = cur_level[0];
            //cout<<"cur value:"<<cur->val<<endl;
            if (cur != NULL) {
                if (cur->left != NULL) {
                    next_level.push_back(cur->left);
                    //cout<<"left value:"<<cur->left->val<<endl;
                }
                if (cur->right != NULL) {
                    next_level.push_back(cur->right);
                    //cout<<"right value:"<<cur->right->val<<endl;
                }
                cur_out.push_back(cur->val);
            } 
            cur_level.erase(cur_level.begin());
        }
    }
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > levelOrder(TreeNode* root) {
        // write code here
        //cout<<"root val:"<<root->val<<endl;
        vector<vector<int> > res;

        if ( root == NULL) {
            return res;
        }
        cur_level_nodes_queue.push_back(root);
        //cout<<"111" << endl; 
        vector<TreeNode* > *cur_level = &cur_level_nodes_queue;
        vector<TreeNode* > *next_level = &next_level_nodes_queue;
        //cout<<"2222" << endl;
        while (!cur_level->empty()) {
            vector<TreeNode* > *tmp = NULL;
            vector<int> cur_out;
            traverse_curlevel(*cur_level, *next_level, cur_out);
            res.push_back(cur_out);
            if (next_level->empty()) {
                break;
            }
            tmp = cur_level;
            cur_level = next_level;
            next_level = tmp;
            
        }
        return res;
    }
};