Lstmxx的空间

655. 输出二叉树

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

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

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

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

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

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

链接

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function getTreeDepth(root: TreeNode | null): number {
  if (root === null) return 0
  return 1 + Math.max(getTreeDepth(root.left), getTreeDepth(root.right))
}

function fill(root: TreeNode | null, res: string[][], depth: number, left: number, right: number) {
  if (root === null) return
  const middle = Math.floor((left + right) / 2)
  res[depth][middle] = "" + root.val
  fill(root.left, res, depth + 1, left, middle - 1)
  fill(root.right, res, depth + 1, middle + 1, right)
}

function printTree(root: TreeNode | null): string[][] {
  let res: string[][] = []
  if (root === null) return res
  const depth = getTreeDepth(root)
  const n = (1 << depth) - 1
  res = Array.from(Array(depth), () => Array(n).fill(""))
  fill(root, res, 0, 0, n)
  return res
};