剑指offer-60、将⼆叉树打印成多⾏

题⽬描述

从上到下按层打印⼆叉树，同⼀层结点从左⾄右输出。每⼀层输出⼀⾏。
给定的⼆叉树是 {1,2,3,#,#,4,5} :

该⼆叉树多⾏打印层序遍历的结果是：

1. [
2. [1],
3. [2,3],
4. [4,5]
5. ]

复制代码

示例1
输⼊：{8,6,10,5,7,9,11}
返回值：[[8],[6,10],[5,7,9,11]]
思路及解答

59题的缩减版
迭代法BFS（广度优先搜索）

1. public class Solution {
2.     ArrayList > Print(TreeNode pRoot) {
3.         //层次打印遍历树
4.         ArrayList > lists = new ArrayList<>();
5.         if(pRoot == null) return lists;
6.         Queue<TreeNode> q = new LinkedList<>();
7.         q.offer(pRoot);
8.         while(!q.isEmpty()){
9.             int size = q.size();
10.             ArrayList<Integer> list = new ArrayList<>();
11.             for(int i = 0; i < size; i++){
12.                 TreeNode temp = q.poll();
13.                 list.add(temp.val);
14.                 if(temp.left != null) q.offer(temp.left);
15.                 if(temp.right != null) q.offer(temp.right);
16.             }
17.             lists.add(list);
18.         }
19.         return lists;
20.     }
21.    
22. }

复制代码

• 时间复杂度：O(n)，每个节点恰好入队和出队各一次
  
• 空间复杂度：O(n)，队列中最多存储n个节
  

递归DFS（深度优先搜索）

虽然层序遍历通常用BFS，但也可以用DFS通过递归隐式维护层级信息来实现

1. import java.util.*;
3. public class Solution {
5.     public ArrayList> levelOrder(TreeNode root) {
6.         ArrayList> result = new ArrayList<>();
7.         if (root == null) return result;
8.         
9.         dfs(root, 0, result);
10.         return result;
11.     }
12.    
13.     private void dfs(TreeNode node, int depth, ArrayList> result) {
14.         if (node == null) return;
15.         
16.         // 如果当前深度对应的列表不存在，创建新列表
17.         if (depth >= result.size()) {
18.             result.add(new ArrayList<>());
19.         }
20.         
21.         // 将当前节点值加入对应深度的列表
22.         result.get(depth).add(node.val);
23.         
24.         // 递归处理左右子树，深度+1
25.         dfs(node.left, depth + 1, result);
26.         dfs(node.right, depth + 1, result);
27.     }
28. }

复制代码

• 时间复杂度：O(n)，每个节点访问一次
  
• 空间复杂度：O(h)，递归栈深度等于树高，最坏情况O(n)
  

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