Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

http://www.lintcode.com/en/problem/binary-tree-level-order-traversal/

Discussion

要非常熟。
递归：对每一个level，记录在相应level的vector上，然后传递child，同时update到level+1，所以单独写了个dfs递归程序（因为有更多的参数要传递）。

Solution

Recursion.

class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Level order a list of lists of integer
     */
public:
    vector<vector<int>> levelOrder(TreeNode *root) {
        // write your code here
        vector<vector<int> > result;
        bfs(root, result, 0);
        return result;
    }
private:
    void bfs(TreeNode *root, vector<vector<int> > &records, int level) {
        if(root ==NULL)
            return;
        if(level == records.size())//records来到了下一个level，所以要extend size
            records.push_back(vector<int> ());
        records[level].push_back(root->val);
        bfs(root->left, records, level+1);
        bfs(root->right, records, level+1);
    }
};

Iteration.用一个queue记录每一个level的node

class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Level order a list of lists of integer
     */
public:
    vector<vector<int>> levelOrder(TreeNode *root) {
        // write your code here
        queue<TreeNode *> myque;
        vector<vector<int>> result;
        if(root == NULL) return result;
        myque.push(root);
        while (myque.empty() == false) {
           int n = myque.size();
            vector<int> onelevel(n,0);
            for(int i=0; i<n; i++) {//pop当前level个
                TreeNode *tmp = myque.front();
                onelevel[i]=tmp->val;
                myque.pop();
                if(tmp->left)
                    myque.push(tmp->left);
                if(tmp->right)
                    myque.push(tmp->right);
            }
            result.push_back(onelevel);
        }
        return result;
    }
};