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();
此句話用的十分巧妙甜橱，通過在未添加新節(jié)點(diǎn)時(shí)就記錄好此時(shí)的隊(duì)列的長(zhǎng)度。便可在下面的循環(huán)中恰好循環(huán)到一層結(jié)束的時(shí)候砾赔。
同時(shí)由于下面會(huì)對(duì)隊(duì)列進(jìn)行操作伞剑，若不實(shí)現(xiàn)將其存入size中足画，將會(huì)導(dǎo)致Queue.size()發(fā)生變化。
啟示：有效的存儲(chǔ)某些臨時(shí)變量捐韩，可將復(fù)雜的操作簡(jiǎn)單化。
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());將數(shù)組前后反轉(zhuǎn)
sort(levOrder.begin(),levOrder.end());將數(shù)組排序
需添加頭文件：
#include <algorithm>
