655. 输出二叉树

在一个 m*n 的二维字符串数组中输出二叉树，并遵守以下规则：
行数 m 应当等于给定二叉树的高度。
列数 n 应当总是奇数。
根节点的值（以字符串格式给出）应当放在可放置的第一行正中间。根节点所在的行与列会将剩余空间划分为两部分（左下部分和右下部分）。你应该将左子树输出在左下部分，右子树输出在右下部分。左下和右下部分应当有相同的大小。即使一个子树为空而另一个非空，你不需要为空的子树输出任何东西，但仍需要为另一个子树留出足够的空间。然而，如果两个子树都为空则不需要为它们留出任何空间。
每个未使用的空间应包含一个空的字符串""。
使用相同的规则输出子树。
示例 1:
输入:
输入:
1
/
2
输出:
[["", "1", ""],
["2", "", ""]]

/*
 * @lc app=leetcode.cn id=655 lang=javascript
 *
 * [655] 输出二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string[][]}
 */
var printTree = function(root) {
     // 构造一个数组，即构造一个height * 2^height - 1的数组
     const height = getHeight(root);
     const len = Math.pow(2,height) - 1;
     let resArr = new Array(height);
     // 构造二维数组
     for(let i = 0;i<resArr.length;i++) {
         resArr[i] = new Array(len);
         resArr[i].fill("")
     }

    //  填充数字
    let i = 0;
    let l = 0;
    let r = len - 1;
    
    // resArr[i][(l + r) / 2] = root.val;
    fill(root, 0, l, r, resArr);
    return resArr;

};
// i：resArr数组的第i层
// l：左边界
// r：右边界
function fill(root, i , l, r, resArr) {
    if (!root) return;
  // 对于根节点来说，他的位置在中位数上
    resArr[i][(l + r)/2] = root.val + '';
    // 对于左子树来说，他的位置在以0为左边界，以根节点位置为右边界的中位数上
    fill(root.left,i+1, l,  (l + r)/2 - 1, resArr)
    fill(root.right,i+1,(l + r)/2 + 1 ,  r, resArr)
}

// 获取树的深度
function getHeight(root) {
    if (!root) return 0;

    return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}
// @lc code=end