Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
ExampleGiven binary tree {3,9,20,#,#,15,7},
3
/
9 20
/ \
15 7
return its level order traversal as:[ [3], [9,20], [15,7]]
vector<vector<int>> levelOrder(TreeNode *root) {
// write your code here
queue<TreeNode *> Queue;
vector<vector<int>> levOrder;
TreeNode *node;
if (root == NULL)
return levOrder;
Queue.push(root);
while (!Queue.empty()) {
vector<int> level;
int size = Queue.size();
for (int i = 0; i<Queue.size(); i++) {
node = Queue.front();
Queue.pop();
level.push_back(node->val);
if (node->left != NULL)
Queue.push(node->left);
if (node->right != NULL)
Queue.push(node->right);
}
levOrder.push_back(level);
}
return levOrder;
}
int size = Queue.size();
此句话用的十分巧妙，通过在未添加新节点时就记录好此时的队列的长度。便可在下面的循环中恰好循环到一层结束的时候。
同时由于下面会对队列进行操作，若不实现将其存入size中，将会导致Queue.size()发生变化。
启示：有效的存储某些临时变量，可将复杂的操作简单化。
Leetcode Binary Tree Level Order Traversal 2
return its level order traversal as:[[15,7],[9,20],[3]]
vector<vector<int>> levelOrderBottom(TreeNode *root) {
queue<TreeNode *> Queue;
vector<vector<int>> levOrder;
TreeNode *node;
if(root==NULL)
return levOrder;
Queue.push(root);
while(!Queue.empty()){
vector<int> level;
int size=Queue.size();
for(int i=0;i<size;i++){
node=Queue.front();
Queue.pop();
level.push_back(node->val);
if(node->left!=NULL)
Queue.push(node->left);
if(node->right!=NULL)
Queue.push(node->right);
}
levOrder.push_back(level);
}
reverse(levOrder.begin(),levOrder.end());
return levOrder;
}
reverse(levOrder.begin(),levOrder.end());将数组前后反转
sort(levOrder.begin(),levOrder.end());将数组排序
需添加头文件：
#include <algorithm>
