/**
 * Here are two solutions for this question, it could be solved 
 * by either BFS or pre-order DFS. There is no difference on 
 * time complexity and space complexity for this two solutions,
 * they are both O(n) and O(log n).
 * Besides, DFS has short codes.
 */


struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<vector<int> > levelOrder(TreeNode *root) {
    vector<vector<int> > result;
    // preOrder(root, 0, result);
    levelOrder(root, result);
    return result;
}


void levelOrder(TreeNode *root, vector<vector<int> > &result) {
    if (root == NULL) return;
    queue<TreeNode *> nQueue;
    nQueue.push(root);
    nQueue.push(NULL); // push NULL to indicate level end
    result.push_back(vector<int>());

    while(!nQueue.empty()) {
        TreeNode *n = nQueue.front();
        nQueue.pop();

        // meet level end symbol
        if (n == NULL) {
            // queue has nodes for next level
            if(!nQueue.empty()) {
                nQueue.push(NULL);
                result.push_back(vector<int>());
            }
        } else {
            result[result.size()-1].push_back(n->val);
            if(n->left != NULL) nQueue.push(n->left);
            if(n->right != NULL) nQueue.push(n->right);
        }
    }
}


void preOrder(TreeNode *n, int level, vector<vector<int> > &result) {
    if (n == NULL) return;

    if (level >= result.size()) {
        result.resize(level+1);
    }

    result[level].push_back(n->val);

    preOrder(n->left, level+1, result);
    preOrder(n->right, level+1, result);
}