Binary Tree Level Order Traversal I [Leetcode]

Given a binary tree, return the level order traversal of its nodes' values. (i.e, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

Solution: this problem can be solved in mutiple ways:

1. To generate the level order traversal of the root node, we first need to generate the level order traversals of its left and right children recursively, and then merge them together.
2. BFS
3. DFS: a and b

   /*******************************SOLUTION 1***********************************/

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int> > levelOrder(TreeNode *root) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(root==NULL){
            vector<vector<int> > ret;
            return ret;
        }
        vector<vector<int> > left, right;
        left = levelOrder(root->left);
        right = levelOrder(root->right);
        int numLayer = min(left.size(), right.size());
        for(int i=0; i<numLayer; i++){
            left[i].insert(left[i].end(), right[i].begin(), right[i].end());
        }
        if(left.size()<right.size()){
            left.insert(left.end(), right.begin()+numLayer, right.end());
        }
        left.insert(left.begin(), vector<int>(1, root->val));
        return left;
    }
};

   /*******************************SOLUTION 2***********************************/

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int> > levelOrder(TreeNode *root) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        vector<vector<int> > ret;
        if(root==NULL) return ret;
        queue<TreeNode*> q;
        q.push(root);
        int curNum = 1, nxtNum = 0;
        vector<int> curLayer;
        while(!q.empty()){
            TreeNode* cur = q.front();
            q.pop();
            curLayer.push_back(cur->val);
            if(cur->left!=NULL){
                q.push(cur->left);
                nxtNum++;
            }
            if(cur->right!=NULL){
                q.push(cur->right);
                nxtNum++;
            }
            curNum--;
            if(curNum==0){
                ret.push_back(curLayer);
                curLayer.clear();
                curNum = nxtNum;
                nxtNum = 0;
            }
        }
        return ret;
    }
};