登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 安全 ›剑指offer-22、从上往下打印⼆叉树

剑指offer-22、从上往下打印⼆叉树

慎气 7 天前
题⽬描述

从上往下打印出⼆叉树的每个节点，同层节点从左⾄右打印。
1.png

思路及解答

这个其实就是标准的迭代遍历了
使用队列（Queue）数据结构实现层次遍历：

  • 将根节点入队
  • 循环执行以下操作直到队列为空：

    • 出队一个节点并访问
    • 将该节点的左子节点入队（如果存在）
    • 将该节点的右子节点入队（如果存在）

  1. /**
  2. public class TreeNode {
  3.     int val = 0;
  4.     TreeNode left = null;
  5.     TreeNode right = null;
  6.     public TreeNode(int val) {
  7.     this.val = val;
  8.         }
  9. }
  10. */
  11. public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
  12.         ArrayList<Integer> result = new ArrayList<>();
  13.         if (root == null) {
  14.             return result; // 空树直接返回空列表
  15.         }
  16.         
  17.         Queue<TreeNode> queue = new LinkedList<>();
  18.         queue.offer(root); // 根节点入队
  19.         
  20.         while (!queue.isEmpty()) {
  21.             TreeNode current = queue.poll(); // 出队当前节点
  22.             result.add(current.val); // 访问节点值
  23.             
  24.             // 左子节点入队
  25.             if (current.left != null) {
  26.                 queue.offer(current.left);
  27.             }
  28.             // 右子节点入队
  29.             if (current.right != null) {
  30.                 queue.offer(current.right);
  31.             }
  32.         }
  33.         
  34.         return result;
  35.     }
  36. }
复制代码

  • ​时间复杂度​：O(n)，每个节点被访问一次
  • ​空间复杂度​：O(n)，队列最多存储n个节点

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

使用道具 举报
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
慎气
7 天前

0

粉丝关注

16

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫