题解 | #把二叉树打印成多行#

题目描述
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
例如：
给定的二叉树是{1,2,3,#,#,4,5}

图片说明

该二叉树多行打印层序遍历的结果是
[
[1],
[2,3],
[4,5]
]

方法一：非递归法求解，参考“门头沟学院叫我皮卡丘”的思路

求解思路
对于求解本题，我们用变量deep存储层数信息，子树的层数则为deep+1，依此类推。同时，我们使用deep作为Lists的索引，当deep>=Lists的大小时，说明该层还未被存入过Lists，则建立新的List，存储节点值，再将List存入Lists。当deep<Lists的大小时，说明该层已经被存储过，取出原来存在Lists中的该层List，把节点信息继续存入List。对于非递归的思路，我我们添加map，每次入队的新节点，用map保存<节点，层数>。

图片说明

解题代码

import java.util.*;
public class Solution {
    ArrayList<ArrayList<Integer>> Print(TreeNode root) {
        ArrayList<ArrayList<Integer>> mylists = new ArrayList<>(); // 声明队列
        HashMap<TreeNode, Integer> mymap = new HashMap<>(); // 声明mymap用来存储<节点。层数>
        if (root == null) // 判断是否为空
        {
            return mylists; // 若为空，直接返回Lists
        }
        Deque<TreeNode> hyqueue = new ArrayDeque<>();
        hyqueue.addFirst(root);
        mymap.put(root, 0);
        while (!hyqueue.isEmpty()) // 开始遍历
        {
            root = hyqueue.pollLast(); // 队尾元素出队
            int deep = mymap.get(root);
            if (root.left != null) // 对其左子树进行判断
            {
                hyqueue.addFirst(root.left);
                mymap.put(root.left, deep + 1);
            }
            if (root.right != null) // 对其右子树进行判断
            {
                hyqueue.addFirst(root.right);
                mymap.put(root.right, deep + 1);
            }
            if (mylists.size() <= deep) // 当deep大于Lists的大小时，该层未被存入过Lists
            {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(root.val);
                mylists.add(list);
            } else // deep小于Lists，说明该层存储过Lists
            {
                ArrayList<Integer> list = mylists.get(deep);
                list.add(root.val);
            }
        }
        return mylists; // 返回结果
    }
}

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：对于非递归中引入了新的内存地址空间，空间复杂度为 $O(N)$

方法二：递归法求解

求解思路
对于本题目，我们可以用deep索引出对应的层信息，方便结点直接找到同一层其他结点。我们在保证入队的顺序，即先左子树，后右子树。再保证建立List的顺序。并且选用先序遍历的模板，其余操作参考第一种方法即可。

图片说明

解题代码

import java.util.ArrayList;
public class Solution {
    ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> hylists = new ArrayList<>();
        if (pRoot == null) // 如果根为空值
        {
            return hylists; // 返回hyLists即可
        }
        dfs(pRoot, 0, hylists); // 深度优先搜索
        return hylists;
    }
    private void dfs(TreeNode pRoot, int deep, ArrayList<ArrayList<Integer>> hylists) // 适用于本题目的深度优先
    {
        if (pRoot == null) // 根为空
        {
            return; // 直接返回
        }
        if (deep >= hylists.size()) // 如果deep大于等于Lists的大小，参考第一种方法的解释
        {
            ArrayList<Integer> list = new ArrayList<>();
            list.add(pRoot.val);
            hylists.add(list);
        } 
        else // 如果deep小于Lists的大小，参考第一种方法
        {
            ArrayList<Integer> list = hylists.get(deep);
            list.add(pRoot.val);
        }
        dfs(pRoot.left, deep + 1, hylists); // 对其左子树进行深度优先搜索即可
        dfs(pRoot.right, deep + 1, hylists); // 对其右子树进行深度优先搜索即可
    }
}

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：对于非递归中引入了新的内存地址空间，空间复杂度为 $O(N)$