LeetCode-面试经典-150-题-102.-二叉树的层序遍历广度优先搜索bfs
目录
(LeetCode 面试经典 150 题) 102. 二叉树的层序遍历（广度优先搜索bfs）
题目：
思路：广度优先搜索bfs，时间复杂度0(n)。
广度优先搜索bfs，每次遍历该层的数量即可。
C++版本：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if(root==nullptr) return ans;
queue<TreeNode *> qu;
qu.push(root);
// 广度优先搜索bfs
while(qu.size()){
// 每次遍历该层的数量
int n=qu.size();
vector<int> v;
while(n--){
TreeNode * tmp=qu.front();
qu.pop();
v.push_back(tmp->val);
if(tmp->left!=nullptr) qu.push(tmp->left);
if(tmp->right!=nullptr) qu.push(tmp->right);
}
ans.push_back(v);
}
return ans;
}
};JAVA版本：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans=new ArrayList<>();
if(root==null) return ans;
Queue<TreeNode> qu=new LinkedList<>();
qu.add(root);
while(!qu.isEmpty()){
int n=qu.size();
List<Integer> v=new ArrayList<>();
while(n>0){
n--;
TreeNode tmp=qu.poll();
v.add(tmp.val);
if(tmp.left!=null) qu.add(tmp.left);
if(tmp.right!=null) qu.add(tmp.right);
}
ans.add(v);
}
return ans;
}
}GO版本：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func levelOrder(root *TreeNode) [][]int {
ans:=[][]int{}
if root==nil {return ans}
qu:=[]*TreeNode{root}
for len(qu)!=0 {
n:=len(qu)
v:=[]int{}
for i:=0;i<n;i++ {
tmp:=qu[0]
qu=qu[1:]
v=append(v,tmp.Val)
if tmp.Left!=nil {qu=append(qu,tmp.Left)}
if tmp.Right!=nil {qu=append(qu,tmp.Right)}
}
ans=append(ans,v)
}
return ans
}