方法:
总体思想:
用队列实现对树的遍历.
两层代码块:
1, 将每一层的节点放入到队列中
2, 然后对这一层的节点进行遍历, 将这些节点放入到 temp 临时变量中
遍历的过程中, 将每一个节点删除 pop, 并且将下一层的节点放入到队列中
3, 遍历完将 temp 添加到 res 中, 同时检查队列是否为空, 直到空的时候, 完成遍历, 返回 res
- * 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>> levelOrderBottom(TreeNode* root)
- {
- vector<vector<int>> res;// 结果
- if(root==NULL)
- return res;
- queue<TreeNode*> q;// 定义一个队列, 用来放树
- q.push(root);// 先把整棵树放进去, 这个队列后面一直在补充子节点,
- {
- vector<int> temp;// 放每一层的节点
- int len = q.size();//len 是每一层的节点数, 因为这个队列会一直向后面补充节点, 所以设为定值, 这样当前层的节点数遍历完了之后, 就继续下一层
- for(int i=0;i<len;i++)
- {
- TreeNode* now = q.front();// 获取队列的第一个节点
- q.pop();// 弹出
- temp.push_back(now->val);// 将这个节点放入到 temp
- if(now->left!=NULL) q.push(now->left);// 然后看这个节点左右子节点是否存在, 存在的话放进去
- if(now->right!=NULL) q.push(now->right);
- }// 这个 for 循环完了之后, 不仅放这一层的所有节点都放进 temp, 而且, 也把这些节点 pop 出去了, 而且, 也把这一层的每一个节点的左右子节点都放入到了队列中, 也就是将当前层的节点 pop, 下一层的所有节点都放进去了
- res.insert(res.begin(), temp);// 将临时变量保存到结果中 (从前面插入)
- }
- return res;
- }
- };
来源: http://www.bubuko.com/infodetail-3099042.html