聊聊从上到下打印二叉树

 

Leetcode :

I：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof II：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof III：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof

“GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_25_levelOrder/Solution.java

从上到下打印二叉树 I

“题目描述 ：从上到下打印出二叉树的聊聊每个节点，同一层的从上叉树节点按照从左到右的顺序打印。例如：给定二叉树: [3,到下打印9,20,null,null,15,7],

     3     / \   9  20  /  \ 15   7 

返回：

[3,9,20,15,7] 

提示：节点总数 <= 1000

解题思路：

题目要求的二叉树的 从上至下 打印(即按层打印)，又称为二叉树的聊聊 广度优先搜索(BFS)。 BFS 通常借助 队列 的从上叉树先入先出特性来实现。

算法流程：

特例处理： 当树的到下打印根节点为空，则直接返回空列表 [] ; 初始化： 打印结果列表 res = [] ，网站模板聊聊包含根节点的从上叉树队列 queue = [root] ; BFS 循环： 当队列 queue 为空时跳出; 出队： 队首元素出队，记为 node; 打印： 将 node.val 添加至列表 tmp 尾部; 添加子节点： 若 node 的到下打印左(右)子节点不为空，则将左(右)子节点加入队列 queue ; 返回值： 返回打印结果列表 res 即可。聊聊

复杂度分析：

时间复杂度 O(N)： N为二叉树的从上叉树节点数量，即 BFS 需循环 N次。到下打印 空间复杂度 O(N) ：最差情况下，聊聊即当树为平衡二叉树时，从上叉树最多有 N/2 个树节点同时在 queue 中，到下打印使用 O(N) 大小的额外空间。 package com.nateshao.sword_offer.topic_25_levelOrder; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; /**  * @date Created by 邵桐杰 on 2021/11/29 14:57  * @微信公众号 程序员千羽  * @个人网站 www.nateshao.cn  * @博客 https://nateshao.gitee.io  * @GitHub https://github.com/nateshao  * @Gitee https://gitee.com/nateshao  * Description: 从上到下打印二叉树 思路：利用队列（链表）辅助实现。服务器租用  *  * add 增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常  * remove 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常  * element 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常  * offer 添加一个元素并返回true 如果队列已满，则返回false  * poll 移除并返问队列头部的元素 如果队列为空，则返回null  * peek 返回队列头部的元素 如果队列为空，则返回null  * put 添加一个元素 如果队列满，则阻塞  * take 移除并返回队列头部的元素 如果队列为空，则阻塞  */ public class Solution {      /**      *  队列      *      * @param root      * @return      */     public int[] levelOrder(TreeNode root) {          if (root == null) return new int[0];//空树则返回空数组         ArrayList<Integer> list = new ArrayList<>();// 申请一个动态数组 ArrayList 动态添加节点值         Queue<TreeNode> queue = new LinkedList<>();         queue.offer(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);// 右子节点入队         }         // 将 ArrayList 转为 int数组并返回         int[] res = new int[list.size()];         for (int i = 0; i < res.length; i++) {              res[i] = list.get(i);         }         return res;     }     /服务器托管