【2022-08-22每日一题】655. 输出二叉树

2022-08-22每日一题：655. 输出二叉树

• 难度：Medium
• 标签：树 、 深度优先搜索 、 广度优先搜索 、 二叉树

给你一棵二叉树的根节点 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 。

示例 1：

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

示例 2：

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

提示：

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

方法一：深度优先遍历

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func calDepth(node *TreeNode) int {
    h := 0
    if node.Left != nil {
        h = calDepth(node.Left) + 1
    }
    if node.Right != nil {
        h = max(h, calDepth(node.Right)+1)
    }
    return h
}

func printTree(root *TreeNode) [][]string {
    height := calDepth(root)
    m := height + 1
    n := 1<<m - 1
    ans := make([][]string, m)
    for i := range ans {
        ans[i] = make([]string, n)
    }
    var dfs func(*TreeNode, int, int)
    dfs = func(node *TreeNode, r, c int) {
        ans[r][c] = strconv.Itoa(node.Val)
        if node.Left != nil {
            dfs(node.Left, r+1, c-1<<(height-r-1))
        }
        if node.Right != nil {
            dfs(node.Right, r+1, c+1<<(height-r-1))
        }
    }
    dfs(root, 0, (n-1)/2)
    return ans
}

func max(a, b int) int {
    if b > a {
        return b
    }
    return a
}

方法二：广度优先遍历

func calDepth(root *TreeNode) int {
    h := -1
    q := []*TreeNode{root}
    for len(q) > 0 {
        h++
        for n := len(q); n > 0; n-- {
            node := q[0]
            q = q[1:]
            if node.Left != nil {
                q = append(q, node.Left)
            }
            if node.Right != nil {
                q = append(q, node.Right)
            }
        }
    }
    return h
}

func printTree(root *TreeNode) [][]string {
    height := calDepth(root)
    m := height + 1
    n := 1<<m - 1
    ans := make([][]string, m)
    for i := range ans {
        ans[i] = make([]string, n)
    }
    type entry struct {
        node *TreeNode
        r, c int
    }
    q := []entry{{root, 0, (n - 1) / 2}}
    for len(q) > 0 {
        e := q[0]
        q = q[1:]
        node, r, c := e.node, e.r, e.c
        ans[r][c] = strconv.Itoa(node.Val)
        if node.Left != nil {
            q = append(q, entry{node.Left, r + 1, c - 1<<(height-r-1)})
        }
        if node.Right != nil {
            q = append(q, entry{node.Right, r + 1, c + 1<<(height-r-1)})
        }
    }
    return ans
}

LeetCode题库地址

• https://leetcode.cn/problems/print-binary-tree