655. 输出二叉树

题目描述

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

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

返回构造得到的矩阵 res 。

示例 1：

输入：root = [1,2]
输出： [["",“1”,""], [“2”,"",""]]

示例 2：

输入：root = [1,2,3,null,4]
输出： [["","","",“1”,"","",""], ["",“2”,"","","",“3”,""], ["","",“4”,"","","",""]]

提示：

树中节点数在范围 [1, 2¹⁰] 内
-99 <= Node.val <= 99
树的深度在范围 [1, 10] 内

解法一：DFS

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func max(nums ...int) int {
    res := nums[0]
    for _, num := range nums {
        if num > res {
            res = num
        }
    }
    return res
}

func printTree(root *TreeNode) [][]string {
    var getHeight func(root *TreeNode) int
    getHeight = func(root *TreeNode) int {
        if nil == root {
            return -1
        }
        return max(getHeight(root.Left), getHeight(root.Right)) + 1
    }
    height := getHeight(root)
    m, n := height+1, int(math.Pow(2, float64(height+1))-1)
    ans := make([][]string, m)
    for i := 0; i < m; i++ {
        ans[i] = make([]string, n)
    }
    var place func(i, j int, root *TreeNode)
    place = func(i, j int, root *TreeNode) {
        if nil == root {
            return
        }
        ans[i][j] = fmt.Sprintf("%d", root.Val)
        t := int(math.Pow(2, float64(height-i-1)))
        place(i+1, j-t, root.Left)
        place(i+1, j+t, root.Right)
    }
    place(0, (n-1)/2, root)
    return ans
}