LeetCode655

在一个 m*n 的二维字符串数组中输出二叉树，并遵守以下规则：

1. 行数 m 应当等于给定二叉树的高度。

2. 列数 n 应当总是奇数。

3. 根节点的值（以字符串格式给出）应当放在可放置的第一行正中间。根节点所在的行与列会将剩余空间划分为两部分（左下部分和右下部分）。你应该将左子树输出在左下部分，右子树输出在右下部分。左下和右下部分应当有相同的大小。即使一个子树为空而另一个非空，你不需要为空的子树输出任何东西，但仍需要为另一个子树留出足够的空间。然而，如果两个子树都为空则不需要为它们留出任何空间。

4. 每个未使用的空间应包含一个空的字符串””。

5. 使用相同的规则输出子树。

示例 1:

输入:
1
/
2
输出:
[[“”, “1”, “”],
[“2”, “”, “”]]
示例 2:

输入:
1
/
2 3

4```
输出:
[[“”, “”, “”, “1”, “”, “”, “”],
[“”, “2”, “”, “”, “”, “3”, “”],
[“”, “”, “4”, “”, “”, “”, “”]]
示例 3:

输入:
1
/
2 5
/
3
/
4
输出:
[[“”, “”, “”, “”, “”, “”, “”, “1”, “”, “”, “”, “”, “”, “”, “”]
[“”, “”, “”, “2”, “”, “”, “”, “”, “”, “”, “”, “5”, “”, “”, “”]
[“”, “3”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”]
[“4”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”]]
注意: 二叉树的高度在范围 [1, 10] 中。

先递归求出树的高度,生成矩阵框架,再递归填充节点值.

class Solution {
    List<List<String>> ans = new ArrayList<>();

    public List<List<String>> printTree(TreeNode root) {
        if (root == null) {
            return ans;
        }
        int height = getHeight(root);
        int n = (int) Math.pow(2, height) - 1;
        /** 生成矩阵 */
        for (int i = 0; i < height; i++) {
            ans.add(new ArrayList<>());
            for (int j = 0; j < n; j++) {
                ans.get(i).add("");
            }
        }

        printNode(root, 0, 0, n - 1);

        return ans;
    }

    /**
     * 打印节点
     */
    private void printNode(TreeNode root, int level, int begin, int end) {
        if (root == null) {
            return;
        }
        int index = (begin + end) / 2;
        ans.get(level).set(index, root.val + "");
        printNode(root.left, level + 1, begin, index - 1);
        printNode(root.right, level + 1, index + 1, end);
    }

    /**
     * 树的高度
     */
    private int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftH = getHeight(root.left);
        int rightH = getHeight(root.right);
        return Math.max(leftH, rightH) + 1;
    }


}