【剑指offer】把二叉树打印成多行 --Java实现

题解

层序遍历大家应该都不陌生，这道题最关键的点在于如何保存层数信息，用变量 deep 存储层数信息，子树的 deep+1，该 deep 可以作为 Lists 的索引：

当 deep >= lists 的大小，说明该层还未被存入过 lists，建立新的 list，存结点值，再把 list 存入 lists
当 deep < lists 的大小，说明该层已经被存储过，取出原来存在 lists 中的该层 list，把结点信息继续存入 list

由于递归和非递归算法的特点，将 deep 作为参数传递和作为 map 传递

一、非递归实现

1. 分析

层序遍历的模板是用一个队列，入队每次遇到的非空结点，出队当前最前结点，直到队列为空，遍历完成
现在为了保存层数信息，我们添加了map，每次入队新的结点，map 保存 <结点,层数> 的 <K,V> 对
关于相同层数如何入 lists，前面也讨论这就不赘述了

2. 代码

import java.util.*;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    ArrayList<ArrayList<Integer>> Print(TreeNode root) {
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        HashMap<TreeNode, Integer> map = new HashMap<>();
        if (root == null) {
            return lists;
        }
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.addFirst(root);
        map.put(root, 0);
        while (!queue.isEmpty()) {
            root = queue.pollLast();
            int deep = map.get(root);
            if (root.left != null) {
                queue.addFirst(root.left);
                map.put(root.left, deep + 1);
            }
            if (root.right != null) {
                queue.addFirst(root.right);
                map.put(root.right, deep + 1);
            }
            if (lists.size() <= deep) {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(root.val);
                lists.add(list);
            } else {
                ArrayList<Integer> list = lists.get(deep);
                list.add(root.val);
            }
        }
        return lists;
    }

}

3. 复杂度

时间复杂度： $O(n)$
空间复杂度： $O(n)$

二、递归实现

1. 分析

其实我们层序遍历一般不会用递归实现，但是这道题比较特殊，特殊之处在于，保存层数的 deep 可以索引出对应的层信息，方便结点直接找到同一层其他结点
我们考虑的问题就变成如何让同一层结点从左到右依次打印，第一个要点肯定是保证入队的顺序，先左子树，后右子树，再一个要点是需要保证建立 list 的顺序，即上一层的 list 先建立先存储进 lists，综合考虑，选用前序遍历的模板
关于相同层数如何入 lists，前面也讨论这就不赘述了

2. 代码

import java.util.ArrayList;


/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        if (pRoot == null) {
            return lists;
        }
        dfs(pRoot, 0, lists);
        return lists;
    }

    private void dfs(TreeNode pRoot, int deep, ArrayList<ArrayList<Integer>> lists) {
        if (pRoot == null) {
            return;
        }
        if (deep >= lists.size()) {
            ArrayList<Integer> list = new ArrayList<>();
            list.add(pRoot.val);
            lists.add(list);
        } else {
            ArrayList<Integer> list = lists.get(deep);
            list.add(pRoot.val);
        }
        dfs(pRoot.left, deep + 1, lists);
        dfs(pRoot.right, deep + 1, lists);
    }

}

3. 复杂度

时间复杂度： $O(n)$
空间复杂度： $O(n)$