求二叉树的层序遍历_

Java

牛客365927066号

不用递归的迭代写法

public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if(root == null) return result;
        LinkedList<TreeNode> linkedList = new LinkedList<>();
        for (linkedList.add(root);linkedList.size()!=0;) {
            ArrayList<Integer> tempList = new ArrayList<>();
            for (int i = linkedList.size(); i > 0; i--) {
                TreeNode tn = linkedList.pop();
                tempList.add(tn.val);
                if (tn.left != null) linkedList.addLast(tn.left);
                if (tn.right != null) linkedList.addLast(tn.right);
            }
            result.add(tempList);
        }
        return result;
    }
}

发表于 2025-09-15 20:56:55 回复(0)

Java

求求来个offer可怜我吧

递归写法

public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        dfs(root, 0, res);
        return res;
    }

    private void dfs(TreeNode node, int level, ArrayList<ArrayList<Integer>> res) {
        if (node == null) return;

        // 如果当前层还没有创建，先创建一个空的列表
        if (res.size() == level) {
            res.add(new ArrayList<>());
        }

        // 将当前节点的值加入当前层
        res.get(level).add(node.val);

        // 递归处理左右子树，层数 +1
        dfs(node.left, level + 1, res);
        dfs(node.right, level + 1, res);
    }

发表于 2025-07-09 22:23:31 回复(0)

Java

亲爱的伱

public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        ArrayList<Integer> level = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque<>();
        if(root == null){
            return ret;
        }
        TreeNode curEnd = root;
        queue.add(root);
        TreeNode nextEnd = null;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
                nextEnd = node.left;
            }
            if (node.right != null) {
                queue.add(node.right);
                nextEnd = node.right;
            }
            if (node == curEnd) {
                ret.add(level);
                level = new ArrayList<>();
                curEnd = nextEnd;
            }
        }
        return ret;
    }

编辑于 2024-02-06 10:59:29 回复(0)

Java

我头像是啥树

public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {

// write code here

ArrayList<ArrayList<Integer>> res = new ArrayList<>();

if(root == null){

return res;

}

ArrayList<TreeNode> listCru = new ArrayList<>();

listCru.add(root);

int count = 0;

int n=1;

while(count < n){

n = listCru.size();

ArrayList<Integer> listres = new ArrayList<>();

for(;count<n;count++){

listres.add(listCru.get(count).val);

if(listCru.get(count).left != null){

listCru.add(listCru.get(count).left);

}

if(listCru.get(count).right != null){

listCru.add(listCru.get(count).right);

}

n = listCru.size();

res.add(listres);

}

return res;

}

发表于 2023-10-19 11:11:23 回复(0)

Java

李克雷

public class Solution {
    /**
     * 给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
     *
     *
     * @param root TreeNode类
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (null == root) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        ArrayList<Integer> currList = new ArrayList<>();
        int rootSize  = queue.size();
        while (!queue.isEmpty()) {
            TreeNode top = queue.poll();
            currList.add(top.val);
            if (top.left != null) {
                queue.offer(top.left);
            }
            if (top.right != null) {
                queue.offer(top.right);
            }
            //如果当前层数的所有节点存储完成
            if (currList.size() == rootSize) {
                result.add(currList);
                currList = new ArrayList<>();
                //队列的size即为下层节点总数
                rootSize = queue.size();
            }
        }
        return result;
    }
}

发表于 2023-10-12 16:30:14 回复(0)

Java

牛客880056622号


	import java.util.*;

public class Solution {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        layer(root, 0);
        return ans;
    }

    public void layer (TreeNode root, int layerNum){
        ArrayList<Integer> temp = new ArrayList<Integer>();
        if(root == null){
            return;
        }
        if(ans.size() <= layerNum){
            temp.add(root.val);
            ans.add(temp);
        }else{
            ans.get(layerNum).add(root.val);
        }
        layer(root.left, layerNum + 1);
        layer(root.right, layerNum + 1);
    }
}

发表于 2023-09-24 16:36:24 回复(0)

Java

牛客781396821号

没想到什么好的办法来记录树的行数

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    ArrayList<TreeNode> list = new ArrayList<TreeNode>();
    ArrayList<Integer> listHor = new ArrayList<Integer>();
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        // list用来将Tree转换成队列
        list = new ArrayList<TreeNode>();
        // listHor用来储存Tree的行数
        listHor = new ArrayList<Integer>();
        if (root == null) {
            return result;
        }
        list.add(root);
        listHor.add(0);
        int count = 1;
        int j = 0;
        ArrayList<Integer> res = new ArrayList<Integer>();
        int oldIndex = 0;
        for (int i = 0; i < list.size(); i++) {
            // 确认现在的行数
            int index = listHor.get(i);
            // 如果换行了，就将res添加到result中
            if (index != oldIndex) {
                if (!res.isEmpty()) {
                    result.add(res);
                }
                res = new ArrayList<Integer>();
                oldIndex = index;
            }
            // 获取Node，并将它的孩子放入队列中，同时根据现在的行数添加其孩子的行数
            TreeNode node = list.get(i);
            if (node.left != null) {
                list.add(node.left);
                listHor.add(index + 1);
            }
            if (node.right != null) {
                list.add(node.right);
                listHor.add(index + 1);
            }
            // 添加到res中
            res.add(node.val);
        }
        result.add(res);
        return result;
    }
}

发表于 2023-08-28 12:23:13 回复(0)

Java

牛客429226965号

class Solution:

def levelOrder(self , root: TreeNode) -> List[List[int]]:

# write code here

if root == None:

return []

que = []

que.append(root)

reslut = []

while len(que) != 0:

temp = []

n = len(que)

for i in range(n):

root = que.pop(0)

temp.append(root.val)

if root.left != None:

que.append(root.left)

if root.right != None:

que.append(root.right)

reslut.append(temp)

return reslut

发表于 2023-08-09 11:25:55 回复(0)

Java

豚豚正在背八股

public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

*

* @param root TreeNode类

* @return int整型ArrayList<ArrayList<>>

* 用BFS做---队列--------广度遍历算法

*/

ArrayList<ArrayList<Integer>> arrys = null;

//尝试用递归来做

private void doFunction(TreeNode node,int index){

if(node==null){

return;

}

//注意这里用>=不能用==,>=表示该层已经创建，直接添加数据到集合即可

if(arrys.size()>=index){

ArrayList<Integer> arry = arrys.get(index-1);

arry.add(node.val);

arrys.set(index-1,arry);

//代表存储该层数据的集合未创建，需创建新子集合

}else{

ArrayList<Integer> arry = new ArrayList<>();

arry.add(node.val);

arrys.add(arry);

}

doFunction(node.left,index+1);

doFunction(node.right,index+1);

}

public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {

arrys = new ArrayList<>();

//执行递归

this.doFunction(root,1);

return arrys;

}

发表于 2023-08-07 11:25:19 回复(0)

Java

DDwu

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> q = new ArrayDeque<TreeNode>();
        q.add(root);
        while (!q.isEmpty()) {
            ArrayList<Integer> row = new ArrayList<>();
            int n = q.size();
            for (int i = 0; i < n; i++) {
                TreeNode temp = q.poll();
                row.add(temp.val);
                if (temp.left != null) q.add(temp.left);
                if (temp.right != null) q.add(temp.right);
            }
            res.add(row);
        }
        return res;
    }
}

发表于 2023-07-22 20:26:28 回复(0)

Java

牛客619390210号

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     *
     * @param root TreeNode类
     * @return int整型ArrayList<ArrayList<>>
     */
    private Map<Integer, ArrayList<Integer>> retMap = new
    HashMap<Integer, ArrayList<Integer>>(16);

    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>>  retList = new ArrayList<>(16);
        //从根节点开始
        levelOrderNext(root, 0);
        int i = 0;
        Iterator<Map.Entry<Integer, ArrayList<Integer>>> iterator = retMap.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Integer, ArrayList<Integer>> next = iterator.next();
            retList.add(next.getValue());
        }
        return retList;

    }
    //层级遍历，递归完成。简单易理解
    public void levelOrderNext(TreeNode root, int num) {
        if (root == null) {
            return;
        }
        if (retMap.get(num) == null) {
            ArrayList<Integer> list = new ArrayList<>(8);
            list.add(root.val);
            retMap.put(num, list);
        } else {
            ArrayList<Integer> list = retMap.get(num);
            list.add(root.val);
            retMap.put(num, list);
        }
        TreeNode leftNode =  root.left;
        TreeNode rightNode =  root.right;
        num++;
        levelOrderNext(leftNode, num);
        levelOrderNext(rightNode, num);
    }
}

发表于 2023-04-19 17:18:27 回复(0)

Java

牛客239032933号

/**

*

* @param root TreeNode类

* @return int整型ArrayList<ArrayList<>>

*/

public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {

// write code here

ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();

level(root,list,0);

return list;

}

public void level (TreeNode root,ArrayList<ArrayList<Integer>> list,int i) {

// write code here

if(root!=null){

if(list.size()==i){

list.add(i,new ArrayList<Integer>());

}

list.get(i).add(root.val);

level(root.left,list,i+1);

level(root.right,list,i+1);

}

发表于 2023-03-07 22:17:12 回复(0)

Java

牛客218391299号

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        return bfs(root);
    }

    private ArrayList<ArrayList<Integer>> bfs(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offerLast(root);
        int size;
        while (!queue.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<>();
            size = queue.size();
            for (int i = 0; i <= size - 1; i++) {
                TreeNode u = queue.pollFirst();
                list.add(u.val);
                if (u.left != null) {
                    queue.offerLast(u.left);
                }
                if (u.right != null) {
                    queue.offerLast(u.right);
                }
            }
            result.add(list);
        }
        return result;
    }
}

发表于 2023-02-15 23:43:30 回复(0)

Java

dynamo1

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     *
     * @param root TreeNode类
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<>();
            int size = queue.size();
            while (size > 0) {
                TreeNode poll = queue.poll();
                list.add(poll.val);
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
                size -- ;
            }
            result.add(list);
        }
        return result;
    }
}

发表于 2022-11-04 22:44:09 回复(0)

Java

键盘都敲坏了.

使用一个队列保存所有节点的值

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        // 定义返回值
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();


        if (root == null){// 传入根节点为空，返回空结果
            return result;
        }


        // 使用LinkedList 当作队列，用于存储遍历到的树节点
        LinkedList<TreeNode> linked = new LinkedList<>();

        linked.add(root); // 首先在队列里添加根节点

        int size; // 用于存储每次获取的链表长度
        TreeNode temp; // 临时节点

        // 只要链表不为空，while继续
        while (!linked.isEmpty()){
            // 获取链表的长度
            size = linked.size();

            // 创建一个list，用于存储当前层的节点值
            ArrayList<Integer> line = new ArrayList<>();

            // 链表有几个元素 就循环几次
            for(int i = 0; i < size; i++){
                // 删除链表头节点，并且将删除的元素返回  (类似于栈的pop，弹出一个元素)
                temp = linked.removeFirst();
                // 将当前层的节点值保存
                line.add(temp.val);

                // left节点不为空 就将left节点添加进链表，作为下一层
                if(temp.left != null){
                    linked.add(temp.left);
                }
                // right节点不为空，就将right节点添加进链表，作为下一层
                if(temp.right != null){
                    linked.add(temp.right);
                }

            }
            // 上面的for循环结束的时候，实际上就已经根据size取出当前层的所有节点，并且存储进了line里，并且也把当前层的所有节点 的 子节点 存入了链表，下次循环会重新计算链表的长度
            
            // 将当前层的所有节点值集合存入result中
            result.add(line);

        }
        // while结束，说明树已经遍历结束，返回result
        return result;
    }
}

发表于 2022-11-02 14:01:28 回复(0)

Java

aklddnddkwndje

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
            
        LinkedList<TreeNode> l = new LinkedList();
        l.push(root);
        ArrayList<ArrayList<Integer>> in1 = new ArrayList();
        while(!l.isEmpty()){
            List<TreeNode> t = new ArrayList();
            ArrayList<Integer> ints = new ArrayList();
            while(!l.isEmpty()){
                TreeNode node = l.pop();
                ints.add(node.val);
                if(null!=node.left)
                    t.add(node.left);
                if(null!=node.right)
                    t.add(node.right);
            }
            in1.add(ints);
            l.addAll(t);
            
        }
        return in1;
    }
    
    
    
    
    
}

发表于 2022-09-03 18:07:53 回复(0)

Java

是小王吖🐅

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
           // write code here
        ArrayList<ArrayList<Integer>> list=new ArrayList<>();
        TreeNode cursor_1=root;
        if(cursor_1==null){
            return list;
        }
        Deque<TreeNode> deque=new LinkedList<>();
        deque.push(cursor_1);
        int length=1;
        while(!deque.isEmpty()){
            int num=0;
            int nextlength=0;
            ArrayList<Integer> sublist=new ArrayList<>();
            while(num<length&&(!deque.isEmpty())){
                cursor_1=deque.poll();
                sublist.add(cursor_1.val);
                if(cursor_1.left!=null){
                    deque.addLast(cursor_1.left);
                    nextlength++;
                }
                if(cursor_1.right!=null){
                    deque.addLast(cursor_1.right);
                    nextlength++;
                }
                num++;
                
            }
            list.add(sublist);
            length=nextlength;
        }
        return list;
    }
}

发表于 2022-08-30 00:15:40 回复(0)

Java

坚果hua

BFS实现层序遍历

public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        ArrayList<ArrayList<Integer>> ans=new ArrayList<>();
        Deque<TreeNode> deque=new ArrayDeque<>();
        deque.addLast(root);
        while(!deque.isEmpty()){
            int size=deque.size();
            ArrayList<Integer> list=new ArrayList<>();
            while(size-->0){
                TreeNode cur=deque.pollFirst();
                list.add(cur.val);
                if(cur.left!=null) deque.addLast(cur.left);
                if(cur.right!=null) deque.addLast(cur.right);
            }
            ans.add(list);
        }
        return ans;
    }

发表于 2022-08-26 14:26:13 回复(0)

Java

你咋不上天呢?

 public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        //使用dummyNode(哨兵节点)的方法
        //如列题的3，9，20，15，7
        //第一层3，在后面加一个null，第二层9，20，后面加一个null，第三层15，7，加一个null
        //最后得：3，null，3，20，null，15，7，null
        //每次判断节点为null，则在队列尾端加一个null，如果节点不是null，则把该节点左右孩子加入队列
        //一开始我们初始化队列为：3，null，好比如 root节点3，不是空，将节点3的左右孩子节点加入队列
        //并将节点3加入列表list，得null，9，20（3节点遍历完去掉，即poll方法），循环到null节点（表明一层结束）
        //要清空list，并在队列尾部加上个null节点
        //每一层结束加一个null节点
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if(root==null){
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        queue.offer(null);
        ArrayList<Integer> list = new ArrayList<Integer>();
        while(!queue.isEmpty()){
           TreeNode node = queue.poll();
            if(node==null){
                //一层结束,并且将这一层的节点值放在list
                if(list.size()==0){//这是为了处理最后一个节点
                    break;
                }
                result.add(list);
                list = new ArrayList<Integer>();
                queue.offer(null);
                continue;
            }
            list.add(node.val);
            if(node.left!=null){
                queue.offer(node.left);
            }
            if(node.right!=null){
                queue.offer(node.right);
            }
        }
        return result;
        
        
        
        // write code here
    }

发表于 2022-08-24 10:55:42 回复(0)

求二叉树的层序遍历

输入

输出

输入

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题