Binary Tree Level Order Traversal

LeetCode #102

Description:

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

Example:

Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]

Idea:

如果不要每层一个vector，那很简单，直接用queue存就行。

要求每层单独出来，则用两个queue，一个pop element出来访问，另一个用来存，一层结束swap两个queue。

Code:

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode *> q_curr, q_next;
        vector<int> level;
        vector<vector<int>> result;
        TreeNode *node=root;

        if(node!=NULL) q_curr.push(node);

        while(!q_curr.empty()){
            while(!q_curr.empty()){
                node=q_curr.front();
                q_curr.pop();
                level.push_back(node->val);

                if(node->left!=NULL) q_next.push(node->left);
                if(node->right!=NULL) q_next.push(node->right);
            }

            swap(q_curr, q_next);
            result.push_back(level);
            level.clear();
        }

        return result;
    }
};