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

题⽬描述

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

思路及解答

这个实在就是标准的迭代遍历了
利用队列（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个节点