【二叉树专题】剑指 Offer 32 – I. 从上到下打印二叉树-跟着帅地玩副业，开拓第二曲线PlayOffer

hi 普通 2023年8月9日上午10:24

非递归方式的层序遍历，利用队列解决

/**
 * 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<int> levelOrder(TreeNode* root) {
        //用队列的方式解决，先加入头结点
        queue<TreeNode*> q;
        vector<int> res;
        if(root) q.push(root);
        //队列不为空时，取出头结点，把左右节点加入队列
        while(q.size()){
            TreeNode* t = q.front();
            q.pop();
            if(t->left) q.push(t->left);
            if(t->right) q.push(t->right);
            res.push_back(t->val);
        }
        return res;
    }
};

0 赞同 0 条回复

今天没时间刷题普通 2023年8月1日下午10:42

时间On，空间On
class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> res;
        queue<TreeNode> q;
        if(!root) return res;

        q.push(*root);
        while(!q.empty())
        {
            TreeNode temp = q.front();
            q.pop();
            res.push_back(temp.val);
            if(temp.left)
            {
                q.push(*temp.left);
            }
            if(temp.right)
            {
                q.push(*temp.right);
            }
        }
        return res;
    }
};

0 赞同 0 条回复

朱志刚普通 2023年7月31日下午3:10

class Solution {
public:
    vector<int> ans;
    vector<int> levelOrder(TreeNode* root) {

        if (!root) {
            return ans;
        }
        queue<TreeNode*> q{{root}};
        while (!q.empty()) {
            auto t = q.front();
            q.pop();
            ans.push_back(t->val);
            if (t->left) {
                q.push(t->left);
            }
            if (t->right) {
                q.push(t->right);
            }
        }
        return ans;
    }
};

通过

0 赞同 0 条回复

小季同学普通 2023年7月26日下午10:20

ts

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function levelOrder(root: TreeNode | null): number[] {
    // 边界判断
    if(root === null) {
        return []
    }
    // 队列
    const queue:TreeNode[] = []
    const result: number[] = []
    queue.push(root)
    while(queue.length > 0) {
        // 将弹出栈的左右节点压入栈中
        let p = queue.shift()
        result.push(p.val)
        if(p.left != null) queue.push(p.left)
        if(p.right != null) queue.push(p.right)
    }
    return result
};

0 赞同 0 条回复

doordie. 普通 2023年7月21日下午4:22

####先序遍历

  public int[] levelOrder(TreeNode root) {
        // 判断特殊情况
        if (root == null) {
            return new int[0];
        }
        //建立一个栈 存放节点
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        // 要返回的数组
        List<Integer> res = new ArrayList<>();
        while (!stack.isEmpty()) {
            TreeNode temp = stack.pop();
            res.add(temp.val);
            if (temp.right != null) {
                stack.push(temp.right);
            }
            if (temp.left != null) {
                stack.push(temp.left);
            }

        }
        int[] result = new int[res.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = res.get(i);
        }
        return result;
    }

层序遍历

 public int[] levelOrderBFS(TreeNode root) {
        // 判断特殊情况
        if (root == null) {
            return new int[0];
        }
        // 存放值的列表
        List<Integer> list = new ArrayList<>();
        // 存放节点的队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        // 遍历过程
        while (!queue.isEmpty()){
            // 获取出队节点
            TreeNode node = queue.poll();
            list.add(node.val);
            if (node.left!=null){
                queue.add(node.left);
            }
            if (node.right!=null){
                queue.add(node.right);
            }
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < res.length;i++){
            res[i] = list.get(i);
        }
        return res;

    }

0 赞同 0 条回复

今天你刷题了嘛普通 2023年7月18日下午10:59

class Solution {
    public int[] levelOrder(TreeNode root) {
        // 层序遍历
        // 需要使用队列
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        List<Integer> result = new ArrayList<>();
        if(root==null) return new int[0];
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur =  queue.poll();
            result.add(cur.val);
            if(cur.left!=null) queue.offer(cur.left);
            if(cur.right!=null) queue.offer(cur.right);
        }
        int[] arr = new int[result.size()];
        for(int i=0; i<result.size(); i++){
            arr[i] = result.get(i);
        }
        return arr;
    }
}

时间复杂度：O（n）
空间复杂度：O（n）

0 赞同 0 条回复

北辰普通 2023年7月18日下午7:51

public int[] levelOrder(TreeNode root) {
            if(root==null) return new int[]{} ;
            List<Integer> list = new ArrayList<>();
            Queue<TreeNode> q = new LinkedList<>();
            q.offer(root);
            while(!q.isEmpty()) {
                TreeNode node = q.poll();
                list.add(node.val);
                if(node.left!=null) q.offer(node.left);
                if(node.right!=null) q.offer(node.right);
            }
            int length = list.size();
            int[] res = new int[length];
            for(int i=0;i<length;i++) {
                res[i] = list.get(i);
            }
            return res;
    }

时间空间复杂度：O(n)

0 赞同 0 条回复

片言莫语普通 2023年7月18日下午4:46

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root == null)    //特殊情况判断别忘记
            return new int[0];
        Queue<TreeNode> queue = new LinkedList<>(); //辅助队列
        List<Integer> res = new ArrayList<>();  //存放结果的列表，因为不知道数组的长度具体为多少，所以用ArrayList
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();   //队列的队首元素弹出
            res.add(node.val);  //弹出的元素进行处理，就是放入到结果集中
            if(node.left != null) queue.add(node.left); //左节点入队列
             if(node.right != null) queue.add(node.right);  //右节点入队列
        }
        int[] arr = new int[res.size()];
        for(int i = 0;i<res.size();i++){
            arr[i] = res.get(i);    //获取列表中的值组成数组
        }
        return arr;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年7月18日上午10:11

class Solution {
    public int[] levelOrder(TreeNode root) {
        // 层序遍历
        if (root==null)
            return new int[0];
        int[] res = new int[1000];
        int count = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode pop = queue.poll();
            res[count++] = pop.val;
            if (pop.left!=null) {
                queue.offer(pop.left);
            }
            if (pop.right!=null) {
                queue.offer(pop.right);
            }
        }
        int[] ans = new int[count];
        for (int i = 0; i < count; i++) {
            ans[i] = res[i];
        }
        return ans;
    }
}

0 赞同 0 条回复

ppopp 普通 2023年7月18日上午12:49

/*
* 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
* 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 levelOrder(TreeNode* root) {
if(root nullptr) return {};
vector ans;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
auto node = q.front();
q.pop();
ans.push_back(node->val);
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
return ans;
}
};

0 赞同 0 条回复

普通 2023年7月17日下午10:16

使用队列完成树的层次遍历
class Solution {
vector invector;
queue<TreeNode> Inqueue;
public:
vector levelOrder(TreeNode root)
{
if(!root) return invector;
Inqueue.push(root);
while(Inqueue.size())
{

           invector.push_back( Inqueue.front()->val); 
         if(Inqueue.front()->left) Inqueue.push(Inqueue.front()->left);
         if(Inqueue.front()->right) Inqueue.push(Inqueue.front()->right);
        Inqueue.pop();
     }
     return invector;

}

};

0 赞同 0 条回复

June 普通 2023年7月17日下午5:03

/**
 * 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 {
        var node *TreeNode = queue.Front().Value.(*TreeNode)
        queue.Remove(queue.Front())
        ans = append(ans,node.Val)

        if node.Left != nil {
            queue.PushBack(node.Left)
        }
        if node.Right != nil {
            queue.PushBack(node.Right)
        }
    }

    return ans
}

0 赞同 0 条回复

NullPointerException 普通 2023年7月17日下午3:01

public int[] levelOrder(TreeNode root) {
//层序遍历使用队列
Queue queue=new LinkedList();
List list =new ArrayList();
if(rootnull)
return new int[0];

    int i = 1;
    queue.add(root);
    while(!queue.isEmpty())
    {
        i =queue.size();
        while(i>0)
        {
            TreeNode temp =queue.remove();
            i--;
            if(temp.left!=null)
            {
                queue.add(temp.left);
            }
            if(temp.right!=null)
            {
                queue.add(temp.right);
            }
            list.add(temp.val);

        }
    }
    int result[]=new int[list.size()];
    for(int j=0;j<result.length;j++)
{
    result[j]=list.get(j);
}
return result;
}

}

0 赞同 0 条回复

V2ero 普通 2023年7月17日上午9:37

时间复杂度O（n），空间复杂度O（n）

function levelOrder(root: TreeNode | null): number[] {
    if(!root) {
        return []
    }
    let queue:TreeNode[] = [root];
    let result:number[] = [];
    while(queue.length) {
        let node = queue.shift();
        result.push(node.val);
        if(node.left) {
            queue.push(node.left);
        }
        if(node.right) {
            queue.push(node.right)
        }
    }
    return result;
}

0 赞同 0 条回复

艺普通 2023年7月16日下午11:16

“`c++
//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:
vector levelOrder(TreeNode* root) {
vector s;
if(root==NULL) return s;
queue q;
if(root) q.push(root);
while(!q.empty())
{
TreeNode *tmp = q.front();
s.push_back(tmp->val);
q.pop();
if(tmp->left) q.push(tmp->left);
if(tmp->right) q.push(tmp->right);
}
return s;
}
};

0 赞同 0 条回复

土豆芋泥包_ 普通 2023年7月16日下午9:43

代码

class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root==null){
            return new int[0];
        }
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> res = new ArrayList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode t = queue.poll();
            res.add(t.val);
            if(t.left!=null) queue.add(t.left);
            if(t.right!=null) queue.add(t.right);
        }

        int[] arr = new int[res.size()];
        for(int i=0;i<res.size();i++){
            arr[i] = res.get(i);
        }
        return arr;
    }
}

0 赞同 0 条回复

神经蛙普通 2023年7月16日下午3:23

/**
    时间复杂度O(n)
    空间复杂度O(n)
*/
class Solution {

    public int[] levelOrder(TreeNode root) {
        LinkedList<Integer> list = new LinkedList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();

        if (root == null) {
            return new int[0];
        }

        // 将头节点入队
        queue.add(root);

        // 遍历处理
        while(!queue.isEmpty()) {
            TreeNode node = queue.removeFirst();
            list.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }

        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); ++i) {
            res[i] = list.get(i);
        }

        return res;
    }
}

0 赞同 0 条回复

Marshan 普通 2023年7月16日上午11:39

class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> res;
        //层序遍历
        if(!root){
            return res;
        }
        queue<TreeNode *> queue;
        queue.push(root);
        while(!queue.empty()){
            TreeNode *tmp = queue.front();
            queue.pop();
            res.push_back(tmp->val);
            if(tmp->left){
                queue.push(tmp->left);
            }
            if(tmp->right){
                queue.push(tmp->right);
            }
        }
        return res;
    }
};

0 赞同 0 条回复

人生何处不青山普通 2023年7月16日上午10:28

TS做法

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function levelOrder(root: TreeNode | null): number[][] {
    const queue: TreeNode[] = [];
    let hh = 0, tt = -1;
    const res: number[][] = [];
    if (root) queue[++tt] = root;
    while (hh <= tt) {
        let len = tt - hh + 1;
        let tmp:number[] = [];
        while (len--) {
            let cur = queue[hh++];
            tmp.push(cur.val);
            (cur.left) && (queue[++tt] = cur.left);
            (cur.right) && (queue[++tt] = cur.right);
        }
        (tmp.length) && (res.push(tmp));
    }
    return res;
};

0 赞同 0 条回复

波雅汉库克普通 2023年7月16日上午10:03

class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> res;
        if(root==nullptr){
            return res;
        }
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int len = q.size();
            while(len--){
                TreeNode* node = q.front();
                res.push_back(node->val);
                q.pop();
                if(node->left!=nullptr){
                    q.push(node->left);
                }
                if(node->right!=nullptr){
                    q.push(node->right);
                }
            }   
        }
        return res;
    }
};

时间：O(n)
空间：O（n)

0 赞同 0 条回复

周小二普通 2023年7月16日上午2:29

class Solution {
    public int[] levelOrder(TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        //辅助队列实现二叉树广度优先
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        List<Integer> result = new ArrayList<>();
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            result.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        int[] res = new int[result.size()];
        for(int i = 0; i < result.size(); i++) {
            res[i] = result.get(i);
        }
        return res;
    }
}

0 赞同 0 条回复

阿尚普通 2023年7月16日上午12:03

//不要求按层打印
class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root == null) return new int[0];

        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            int layerSize = queue.size();

            for(int i = 0; i < layerSize; i++){
                TreeNode node = queue.poll();
                list.add(node.val);

                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
        }

        int[] result = new int[list.size()];

        for(int i = 0; i < list.size(); i++){
            result[i] = list.get(i);
        }

        return result;
    }
}

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月15日下午9:54

Day8：下面是代码

class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root == null) return new int[0];
        Queue<TreeNode> q = new LinkedList<>();
        ArrayList<Integer> tmp = new ArrayList<>();
        q.offer(root);
        while(q.size() != 0){
            TreeNode node = q.poll();
            tmp.add(node.val);

            if(node.left != null) q.offer(node.left);
            if(node.right != null) q.offer(node.right);
        }

        int res[] = new int[tmp.size()];
        for(int i = 0; i < res.length; i++){
            res[i] = tmp.get(i);
        }
        return res;
    }
}

0 赞同 0 条回复

CaCO3 永久会员 2023年7月15日下午8:51

”’java
class Solution {
public int[] levelOrder(TreeNode root) {
if(root null){
return new int[0];
}
Queue queue = new ArrayDeque<>();
List list = new ArrayList<>();
queue.add(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
list.add(node.val);
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
}

    return list.stream().mapToInt(Integer::intValue).toArray();
}

}
”’
时间复杂度O(n)
空间复杂度O(n)

0 赞同 0 条回复

CKX 普通 2023年7月15日下午6:08

func levelOrder(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    res := []int{}
    queue := []*TreeNode{root}  //将头节点存入队列
    for len(queue) > 0 {
        //队列中有元素
        temp := queue[0]    //获取队头元素
        res = append(res, temp.Val)
        queue = queue[1:]   //队头元素出队

        if temp.Left != nil {
            queue = append(queue, temp.Left)
        }
        if temp.Right != nil {
            queue = append(queue, temp.Right)
        }
    }

    return res

}

时间O(n)
空间O(n)

0 赞同 0 条回复

#00456B 普通 2023年7月15日下午5:18

思路

因为要层序遍历，所以就不好采用递归的方法来实现。所以借用queue来实现层序遍历。
首先将root节点放入queue中，然后当queue不为空时进行循环。其中首先记录queue的顶部的数值，然后放到ans中输出。然后判断当前头节点的左右子节点是否为空，如果不为空就放入queue中。直到queue成为一个空队列，说明遍历结束，输出ans数组。

代码

“`cpp
class Solution {
public:
vector levelOrder(TreeNode* root) {
vector ans;
if(root == NULL){
return ans;
}
queue que;
que.push(root);
while(!que.empty()){
TreeNode* temp = que.front();
ans.push_back(temp->val);
if(temp->left) que.push(temp->left);
if(temp->right) que.push(temp->right);
que.pop();
}
return ans;
}
};

0 赞同 0 条回复

远行客普通 2023年7月15日下午5:13

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def levelOrder(self, root:TreeNode) -> list[int]:
        # 从上到下打印二叉树， 广度优先搜索， bfs
        # 使用队列先进先出的特点来实现

        #根结点为空， 返回空列表
        if not root:
            return []

        # 初始化
        res = []
        import collections
        queue = collections.deque()
        queue.append(root)

        # 当队列为空时， 跳出循环
        while queue:
            # 队首元素出队
            node = queue.popleft()
            # 添加到列表尾部
            res.append(node.val)

            # 左子节点如果存在， 加入队列
            if node.left:
                queue.append(node.left)

            # 右子节点如果存在， 加入队列
            if node.right:
                queue.append(node.right)

        return res

    """
    时间复杂度：O(N)
    空间复杂度：O(N)
    """

0 赞同 0 条回复

Luminous 普通 2023年7月15日下午5:13

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
        if(root==null) return new int[0];
        Queue<TreeNode> queue=new LinkedList<>();
        List<Integer> ans=new ArrayList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode node=queue.poll();
            ans.add(node.val);
            if(node.left!=null) queue.add(node.left);
            if(node.right!=null) queue.add(node.right);
        }
        int []res=new int[ans.size()];
        for(int i=0;i<ans.size();i++){
            res[i]=ans.get(i);
        }
        return res;
    }
}

时间复杂度:O(n)
空间复杂度:O(n)

0 赞同 0 条回复

AD钙奶普通 2023年7月15日下午5:10

class Solution {
    public int[] levelOrder(TreeNode root) {
        Deque deque = new ArrayDeque<>();
        if(root == null) return new int[0];
        List list = new ArrayList<>();
        deque.addLast(root);
        while(!deque.isEmpty()) {
            int size = deque.size();
            for(int i = 0; i < size; i ++) {
                TreeNode node = deque.removeFirst();
                list.add(node.val);
                if(node.left != null) deque.addLast(node.left);
                if(node.right != null) deque.addLast(node.right);
            }
        }
        int[] res = new int[list.size()];
        for(int i = 0; i < list.size(); i ++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

时间复杂度O(n) 空间复杂度O(n）

0 赞同 0 条回复

Mooby 普通 2023年7月15日下午2:59

八
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int[] levelOrder(TreeNode root) {
if (root null) return new int[0];
Queue queue = new LinkedList<>() {{ add(root); }};
ArrayList ans = new ArrayList<>();
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
ans.add(node.val);
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
int[] res = new int[ans.size()];
for (int i = 0; i < ans.size(); i++)
res[i] = ans.get(i);
return res;
}
}

0 赞同 0 条回复

枫梓。普通 2023年7月15日下午2:06

class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        vector<int> ans;
        if(!root) return ans;
        que.push(root);
        while(!que.empty()) {
            for(int i = 0; i < que.size(); ++i) {
                TreeNode* temp = que.front();
                que.pop();
                ans.push_back(temp->val);
                if(temp->left) que.push(temp->left);
                if(temp->right) que.push(temp->right);
            }
        }
        return ans;
    }
};

层序遍历空间复杂度O(n) 时间复杂度O(n）

0 赞同 0 条回复

【二叉树专题】剑指 Offer 32 – I. 从上到下打印二叉树

共以下 31 个回答

层序遍历

思路

代码

# 回答此问题取消回复

【二叉树专题】剑指 Offer 32 – I. 从上到下打印二叉树

共以下 31 个回答

层序遍历

思路

代码

# 回答此问题 取消回复

# 回答此问题取消回复