[LeetCode] Binary Tree Level Order Traversal
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).
For example: Given binary tree
return its level order traversal as:
confused what
問題解決の考え方:
すべてのノードを1つのキューで記録します.しかし、ここでトラップは、各層がそれぞれ1つのvectorで表されるべきであるため、対応するnodeが存在する層数を格納するためにキューが必要である.同じレイヤはキュー内で隣接しているに違いないので,この方法で解決できる.
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example: Given binary tree
{3,9,20,#,#,15,7}
, 3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
confused what
"{1,#,2,3}"
means? > read more on how binary tree is serialized on OJ. 問題解決の考え方:
すべてのノードを1つのキューで記録します.しかし、ここでトラップは、各層がそれぞれ1つのvectorで表されるべきであるため、対応するnodeが存在する層数を格納するためにキューが必要である.同じレイヤはキュー内で隣接しているに違いないので,この方法で解決できる.
/**
* 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<vector<int>> result;
if(root==NULL){
return result;
}
queue<int> level;
queue<TreeNode*> queues;
level.push(0);
queues.push(root);
int lastLevel = 0;
vector<int> lastValue;
while(!queues.empty()){
TreeNode* node = queues.front();
int l = level.front();
if(l!=lastLevel){
result.push_back(lastValue);
lastValue.clear();
lastLevel = l;
}
lastValue.push_back(node->val);
queues.pop();
level.pop();
if(node->left!=NULL){
queues.push(node->left);
level.push(l + 1);
}
if(node->right!=NULL){
queues.push(node->right);
level.push(l + 1);
}
}
if(!lastValue.empty()){
result.push_back(lastValue);
}
return result;
}
};