Задача: 655. Print Binary Tree
Сложность: medium

Учитывая корень двоичного дерева, постройте строковую матрицу res с индексом 0 размером m x n, которая представляет собой форматированную раскладку дерева. Форматированная матрица должна быть построена по следующим правилам: высота дерева равна 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.

Пример:

Input: root = [1,2]
Output: 
[["","1",""],
 ["2","",""]]

👨‍💻 Алгоритм:

1⃣Найдите высоту дерева и определите размер матрицы (m x n).

2⃣Рекурсивно разместите узлы в матрице, начиная с корневого узла.

3⃣Верните заполненную матрицу.

😎 Решение:

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

const findHeight = (root) => {
    if (!root) return -1;
    return 1 + Math.max(findHeight(root.left), findHeight(root.right));
}

const fill = (res, root, r, c, height) => {
    if (!root) return;
    res[r][c] = root.val.toString();
    if (root.left) {
        fill(res, root.left, r + 1, c - (1 << (height - r - 1)), height);
    }
    if (root.right) {
        fill(res, root.right, r + 1, c + (1 << (height - r - 1)), height);
    }
}

const printTree = (root) => {
    const height = findHeight(root);
    const m = height + 1;
    const n = (1 << (height + 1)) - 1;
    const res = Array.from({ length: m }, () => Array(n).fill(""));
    fill(res, root, 0, Math.floor((n - 1) / 2), height);
    return res;
}

Ставь 👍 и забирай 📚 Базу знаний