导航：首页 > 互联网科技 >

如何进行python二叉树的层次遍历

发表于：2025-02-06 作者：千家信息网编辑

千家信息网最后更新 2025年02月06日，本篇文章给大家分享的是有关如何进行python二叉树的层次遍历，小编觉得挺实用的，因此分享给大家学习，希望大家阅读完这篇文章后可以有所收获，话不多说，跟着小编一起来看看吧。给定一个二叉树，返回其按层次

千家信息网最后更新 2025年02月06日如何进行python二叉树的层次遍历

本篇文章给大家分享的是有关如何进行python二叉树的层次遍历，小编觉得挺实用的，因此分享给大家学习，希望大家阅读完这篇文章后可以有所收获，话不多说，跟着小编一起来看看吧。

给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。

例如:

给定二叉树: [3,9,20,null,null,15,7],

/ \

9 20

/ \

15 7

返回其层次遍历结果：

[

[3],

[9,20],

[15,7]

]

答案：

 1public List> levelOrder1(TreeNode root) {
 2    Queue queue = new LinkedList();
 3    List> wrapList = new LinkedList>();
 4    if (root == null)
 5        return wrapList;
 6    queue.offer(root);
 7    while (!queue.isEmpty()) {
 8        int levelNum = queue.size();
 9        List subList = new LinkedList();
10        for (int i = 0; i < levelNum; i++) {
11            if (queue.peek().left != null)
12                queue.offer(queue.peek().left);
13            if (queue.peek().right != null)
14                queue.offer(queue.peek().right);
15            subList.add(queue.poll().val);
16        }
17        wrapList.add(subList);
18    }
19    return wrapList;
20}

解析：

LinkedList是个链表，先进先出，levelNum是每一层的节点数量，一层一层的遍历，代码没什么难度，下面再来看一种递归的写法

 1public List> levelOrder(TreeNode root) {
 2    List> res = new ArrayList>();
 3    levelHelper(res, root, 0);
 4    return res;
 5}
 6
 7public void levelHelper(List> res, TreeNode root, int height) {
 8    if (root == null) return;
 9    if (height >= res.size()) {
10        res.add(new LinkedList());
11    }
12    res.get(height).add(root.val);
13    levelHelper(res, root.left, height + 1);
14    levelHelper(res, root.right, height + 1);
15}