陈恒承

输出二叉树

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/print-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这个题，在于分割的地方，我没有定“左右边界的”概念导致构建错误.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string[][]}
 */
var printTree = function (root) {
  /*
       m:二叉树的高度
       n:列树，总是奇数

       看来是递归的构建
   */

  const queue = [root];

  let m = 0;

  while (queue.length > 0) {
    let size = queue.length;
    for (let i = 0; i < size; i++) {
      let node = queue.shift();
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    m++;
  }

  const n = 2 ** m - 1;

  const result = new Array(m);

  for (let i = 0; i < m; i++) {
    result[i] = new Array(n).fill("");
  }

  // 原来左右分割是这样....真是无语了.....
  const dfs = (root, depth, l, r) => {
    if (!root) return;

    let pos = (l + r) >> 1;

    // 取中点
    result[depth][pos] = root.val.toString();

    // 左边界，右边界 !!!我竟然卡在这里
    dfs(root.left, depth + 1, l, pos);

    dfs(root.right, depth + 1, pos, r);
  };
  dfs(root, 0, 0, n);

  return result;
};