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,然后逐层填充。

// date 2023/11/01
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
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)
    }

    fillRes(res, root, 0, 0, length)

    return res
}

func fillRes(res [][]string, node *TreeNode, row, left, right int) {
    if node == nil {
        return
    }
    res[row][(left+right)/2] = fmt.Sprintf("%d", node.Val)
    fillRes(res, node.Left, row+1, left, (left+right)/2)
    fillRes(res, node.Right, row+1, (left+right+1)/2, right)
}

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
}

最后更新于