102. Binary Tree Level Order Traversal

/** * Definition for a binary tree node. * 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) { vector<int> res; vector< vector<int> > all; if (root == nullptr) return all; queue< pair<TreeNode *, int> > q; // the int is a tag indicating which level the node is at int curr_level = 0; TreeNode * curr = root; q.push(make_pair(curr, curr_level)); int prev_level = 0; while(!q.empty()){ pair<TreeNode*, int> p = q.front(); q.pop(); curr = p.first; curr_level = p.second; if (curr->left != nullptr) q.push(make_pair(curr->left, curr_level+1)); if (curr->right != nullptr) q.push(make_pair(curr->right, curr_level+1)); if (curr_level != prev_level){ // finished a previous level! store results, update, move on to the next all.push_back(res); res = {}; prev_level = curr_level; } res.push_back(curr->val); } all.push_back(res); // the last level return all; } };