655 输出二叉树-中等

给你一棵二叉树的根节点 root ，请你构造一个下标从 0 开始、大小为 m x n 的字符串矩阵 res ，用以表示树的 格式化布局 。构造此格式化布局矩阵需要遵循以下规则：

树的 高度 为 height ，矩阵的行数 m 应该等于 height + 1 。 矩阵的列数 n 应该等于 2height+1 - 1 。 根节点 需要放置在 顶行 的 正中间 ，对应位置为 res[0][(n-1)/2] 。 对于放置在矩阵中的每个节点，设对应位置为 res[r][c] ，将其左子节点放置在 res[r+1][c-2height-r-1] ，右子节点放置在 res[r+1][c+2height-r-1] 。 继续这一过程，直到树中的所有节点都妥善放置。 任意空单元格都应该包含空字符串 "" 。 返回构造得到的矩阵 res 。

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/print-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

算法分析：

先构造结果集，然后逐层填充。

// date 2020/02/25
func printTree(root *TreeNode) [][]string {
    depth := findDepth(root) // 行数
    // 列数
    length := 1 << depth - 1
    res := make([][]string, depth)
    for i := 0; i < depth; i++ {
        res[i] = make([]string, length)
    }
    fill(res, root, 0, 0, length)
    return res
}

func fill(res [][]string, t *TreeNode, i, l, r int) {
    if t == nil {
        return
    }
    res[i][(l+r)/2] = fmt.Sprintf("%d", t.Val)
    fill(res, t.Left, i+1, l, (l+r)/2)
    fill(res, t.Right, i+1, (l+r+1)/2, r)
}

func findDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    l, r := findDepth(root.Left), findDepth(root.Right)
    if l > r {
        return l+1
    }
    return r+1
}