Задача: 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⃣Верните заполненную матрицу.

😎 Решение:

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int findHeight(TreeNode* root) {
    if (!root) return -1;
    return 1 + max(findHeight(root->left), findHeight(root->right));
}

void fill(vector<vector<string>>& res, TreeNode* root, int r, int c, int height) {
    if (!root) return;
    res[r][c] = to_string(root->val);
    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);
    }
}

vector<vector<string>> printTree(TreeNode* root) {
    int height = findHeight(root);
    int m = height + 1;
    int n = (1 << (height + 1)) - 1;
    vector<vector<string>> res(m, vector<string>(n, ""));
    fill(res, root, 0, (n - 1) / 2, height);
    return res;
}

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