/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func levelOrder(root *TreeNode) [][]int {
var ans [][]int
if root == nil {
return ans
}
var queue = list.New()
queue.PushBack(root)
for queue.Len() != 0 {
size := queue.Len()
var tmp []int // 中间数组
for i:=0 ; i < size ; i++ {
var node *TreeNode = queue.Front().Value.(*TreeNode)
queue.Remove(queue.Front())
tmp = append(tmp,node.Val)
if node.Left != nil {
queue.PushBack(node.Left)
}
if node.Right != nil {
queue.PushBack(node.Right)
}
}
ans = append(ans,tmp)
}
return ans
}
八
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List> levelOrder(TreeNode root) {
Queue queue = new LinkedList<>();
List<List> res = new ArrayList<>();
if (root != null) queue.add(root);
while (!queue.isEmpty()) {
List tmp = new ArrayList<>();
for (int i = queue.size(); i > 0; i–) {
TreeNode node = queue.poll();
tmp.add(node.val);
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
res.add(tmp);
}
return res;
}
}
共以下 30 个回答
通过
ts
这是一个非递归的中序遍历打印
时间复杂度:O(n)
空间复杂度:O(n)
时间复杂度:O(n)
空间复杂度:O(n)
/**> levelOrder(TreeNode root) {> ret; ());
* 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
vector<vector
if(!root) return ret;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int lz = q.size();
ret.push_back(vector
for(int i = 1; i <= lz; ++i){
auto node = q.front();
q.pop();
ret.back().push_back(node->val);//back()表示对最后一个元素的引用
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
}
return ret;
}
};
c++ 代码在之前一题的基础上改进一些就可以了> cc;> levelOrder(TreeNode root) lever;
class Solution
{
vector<vector
queue<TreeNode> Inqueue;
public:
vector<vector
{
if(!root) return cc;
Inqueue.push(root);
while(Inqueue.size())
{
int l=Inqueue.size();
vector
for(int i=0;i<l;i++)
{
TreeNode* temp=Inqueue.front();
lever.push_back(temp->val);
if(temp->left) Inqueue.push(temp->left);
if(temp->right) Inqueue.push(temp->right);
Inqueue.pop();
}
cc.push_back(lever);
}
return cc;
}
};
“`c++> levelOrder(TreeNode* root) {> res; q; lev;val);
//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:
vector
vector
int i;
if(!root) return res;
queue
q.push(root);
while(!q.empty())
{
int k=q.size();
vector
for(i=0;i
if(tmp->left) q.push(tmp->left);
if(tmp->right) q.push(tmp->right);
}
res.push_back(lev);
}
return res;
}
};
“`
class Solution {//遍历> levelOrder(TreeNode root) { > reuslt =new ArrayList<List >(); temp ; queue =new LinkedList ();();
public List<List
List<List
List
if(root null) return reuslt;
Queue
queue.add(root);
int i= 1;
while(!queue.isEmpty())
{
i =queue.size();
temp =new ArrayList
while(i>0)
{
TreeNode node =queue.remove();
i–;
if(node.left!=null)
{
queue.add(node.left);
}
if(node.right!=null)
{
queue.add(node.right);
}
temp.add(node.val);
}
reuslt.add(temp);
}
return reuslt;
}
}
时间复杂度O(n),空间复杂度O(n)
打卡
略显繁琐
TS模拟队列
时间:o(n)
空间:o(n)
Day8:下面是代码
”’java> levelOrder(TreeNode root) { > re = new ArrayList<>();
class Solution {
public List<List
List<List
if(root null){
}
”’
时间复杂度O(n)
空间复杂度O(n)
思路
和上一题类似,需要层序遍历,但是改为每一层分别用一个vector来存储。
所以在判断queue是否为空之后,先获取当前queue中的节点个数,这个数量表示这一层需要添加左右子节点的节点数,然后根据这个size数量来进行循环,将每一层的vector都push到ans中。最后输出ans。
代码
时间复杂度:O(n)
空间复杂度:O(n)
每一层都打印
时间空间复杂度O(n)
八> levelOrder(TreeNode root) { queue = new LinkedList<>();> res = new ArrayList<>(); tmp = new ArrayList<>();
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List
Queue
List<List
if (root != null) queue.add(root);
while (!queue.isEmpty()) {
List
for (int i = queue.size(); i > 0; i–) {
TreeNode node = queue.poll();
tmp.add(node.val);
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
res.add(tmp);
}
return res;
}
}
双O(n)