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 {3,9,20,#,#,15,7}, 3 / \ 9 20 / \ 15 7return its level order traversal as:[ [3], [9,20], [15,7]
]
解题思路:
求一棵二叉树的各层节点，并且按层存储在二元数组中。利用BFS即可实现。我的博客《二元树的生成、遍历、以及最短最长路径查询》中已经提到，利用队列可实现二元树的横向遍历，这本题中，我们依旧利用队列对树进行BFS，使用两个队列，q表示本层节点，q1表示下层节点，依次进队列，，出队列，便可构造二维向量。
代码如下：
class Solution {public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;vector<int> temp;if(root==NULL) return res;queue<TreeNode*> q;q.push(root);TreeNode *node;while(!q.empty()){queue<TreeNode*> q1;while(!q.empty()){node=q.front();temp.push_back(node->val);q.pop();if(node->left!=NULL){q1.push(node->left);}if(node->right!=NULL){q1.push(node->right);}}res.push_back(temp);q=q1;temp.clear();}return res;}};Binary Tree Level Order Traversal II
Given a binary tree, return thebottom-up level ordertraversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).
For example:Given binary tree{3,9,20,#,#,15,7},
3 / \ 9 20/ \ 15 7
return its bottom-up level order traversal as:
[ [15,7], [9,20], [3]]解题思路：
同Binary Tree Level Order Traversal一样，最后将二元向量翻转即可，代码如下：
class Solution {public:vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> res;vector<int> temp;if(root==NULL) return res;queue<TreeNode*> q;q.push(root);TreeNode* node;while(!q.empty()){queue<TreeNode*> q1;while(!q.empty()){node=q.front();q.pop();temp.push_back(node->val);if(node->left!=NULL)q1.push(node->left);if(node->right!=NULL)q1.push(node->right);}res.push_back(temp);temp.clear();q=q1;}reverse(res.begin(),res.end());return res;}};
细数门前落叶，倾听窗外雨声，
