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

从上到下按层打印⼆叉树同⼀层结点从左⾄右输出。每⼀层输出⼀⾏。给定的⼆叉树是 {1,2,3,#,#,4,5} :​编辑该⼆叉树多⾏打印层序遍历的结果是text[ [1], [2,3], [4,5] ]示例1输⼊{8,6,10,5,7,9,11}返回值[[8],[6,10],[5,7,9,11]]思路及解答59题的缩减版迭代法BFS广度优先搜索javapublic class Solution { ArrayListArrayListInteger Print(TreeNode pRoot) { //层次打印遍历树 ArrayListArrayListInteger lists new ArrayList(); if(pRoot null) return lists; QueueTreeNode q new LinkedList(); q.offer(pRoot); while(!q.isEmpty()){ int size q.size(); ArrayListInteger list new ArrayList(); for(int i 0; i size; i){ TreeNode temp q.poll(); list.add(temp.val); if(temp.left ! null) q.offer(temp.left); if(temp.right ! null) q.offer(temp.right); } lists.add(list); } return lists; } }时间复杂度O(n)每个节点恰好入队和出队各一次空间复杂度O(n)队列中最多存储n个节递归DFS深度优先搜索虽然层序遍历通常用BFS但也可以用DFS通过递归隐式维护层级信息来实现javaimport java.util.*; public class Solution { public ArrayListArrayListInteger levelOrder(TreeNode root) { ArrayListArrayListInteger result new ArrayList(); if (root null) return result; dfs(root, 0, result); return result; } private void dfs(TreeNode node, int depth, ArrayListArrayListInteger result) { if (node null) return; // 如果当前深度对应的列表不存在创建新列表 if (depth result.size()) { result.add(new ArrayList()); } // 将当前节点值加入对应深度的列表 result.get(depth).add(node.val); // 递归处理左右子树深度1 dfs(node.left, depth 1, result); dfs(node.right, depth 1, result); }