C++ BFS solution using level indexing


#1

vector<vector > Solution::levelOrder(TreeNode* A) {
vector<vector > res;
if (nullptr == A) return res;

	queue<pair<TreeNode*, int>> nodes; //pair of Tree node  and level id
	int level = 0;
	nodes.push(make_pair(A, level));
	res.push_back(vector<int>());

	while (nodes.empty() == false)
	{
		auto curr = nodes.front();
		nodes.pop();


		if (curr.first->left)
			nodes.push(make_pair(curr.first->left,  curr.second + 1));
		if (curr.first->right)
			nodes.push(make_pair(curr.first->right,  curr.second + 1));

		if (curr.second != level) //reached new level
		{
			res.push_back(vector<int>());
			++level;
		}

		res[level].push_back(curr.first->val);
	}

	return res;

}