首页 > 代码库 > 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 {3,9,20,#,#,15,7},
3 / 9 20 / 15 7
return its level order traversal as:
[ [3], [9,20], [15,7]]
BFS思路：层序遍历用队列的先进先出来实现。最开始的想法是想在一个队列中通过统计某层得节点个数来完成把每一层存储到vector中，发现搞不出来。后来看到有人的代码用两个队列来实现~确实是个好办法。
pre队列装上一层得节点，然后把pre中节点的左右孩子全部放到cur中，放一次，就把pre中节点存储在temp中，然后从pre中pop，当pre为空时，那么就把temp放到结果res中，然后清空temp准备存储下一层，最后把cur赋给pre，清空cur。进而重复上面的步骤。
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: void qClear(queue<TreeNode*>& a) { while (!a.empty()) { a.pop(); } } vector<vector<int>> levelOrder(TreeNode *root) { vector<vector<int>> res; vector<int> temp; if(root==NULL) return res; queue<TreeNode*> pre,cur; pre.push(root); do { TreeNode* node=pre.front(); if(node->left!=NULL){ cur.push(node->left); } if(node->right!=NULL){ cur.push(node->right); } temp.push_back(pre.front()->val); pre.pop(); if(pre.empty()){//pre中所有节点清空 res.push_back(temp); temp.clear(); pre=cur; qClear(cur); } }while (!pre.empty()); return res; }};
DFS（转载，原文链接）：
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {private: vector<vector<int> > ret;public: void solve(int dep, TreeNode *root) { if (root == NULL) return; if (ret.size() > dep) { ret[dep].push_back(root->val); } else { vector<int> a; a.push_back(root->val); ret.push_back(a); } solve(dep + 1, root->left); solve(dep + 1, root->right); } vector<vector<int> > levelOrder(TreeNode *root) { // Start typing your C/C++ solution below // DO NOT write int main() function ret.clear(); solve(0, root); return ret; }};
Binary Tree Level Order Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。