Binary Tree Levelorder Traversal

题目：

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

接口：

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

    }
};

分析：

这道levelorder traversal可以用两种方法做，也就是DFS和BFS，这里用BFS，DFS后边补上

定义结点：

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

解法：

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
        if (root == NULL) {
            return vector<vector<int> >();
        }

        vector<vector<int> > results;
        queue<TreeNode*> Q;
        Q.push(root);

        while (!Q.empty() ) {
            int size = Q.size();
            vector<int> level;
            for (int i = 0; i < size; i++) {
                TreeNode* temp = Q.front();
                Q.pop();

                level.push_back(temp->val);
                if (temp->left != NULL) {
                    Q.push(temp->left);
                }
                if (temp->right != NULL) {
                    Q.push(temp->right);
                }
            }
            results.push_back(level);
        }
        return results;
    }
};