Задача: 606. Construct String from Binary Tree
Сложность: medium

Дано бинарное дерево, необходимо вернуть его строковое представление, используя прямой обход (preorder traversal) и правила со скобками:
Скобки для детей обязательны, если есть правый ребёнок
Пропускать пустые скобки, кроме случая, когда отсутствует левый, но есть правый ребёнок

Пример:

Input: root = [1,2,3,4]
Output: "1(2(4))(3)"
Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the empty parenthesis pairs. And it will be "1(2(4))(3)".

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

1⃣Инициализация и рекурсия
Начинаем с корневого узла бинарного дерева и выполняем прямой обход (preorder traversal) с использованием рекурсии. Для каждого узла добавляем его значение к строке результата.

2⃣Обработка дочерних узлов
Случай 1: Если у узла есть оба дочерних узла (левый и правый), оборачиваем результаты прямого обхода для обоих дочерних узлов в скобки. Случай 2: Если у узла нет дочерних узлов, пропускаем скобки для них. Случай 3: Если у узла есть только левый дочерний узел, обходим его и добавляем результат в скобках, пропуская пустые скобки для правого дочернего узла. Случай 4: Если у узла есть только правый дочерний узел, добавляем пустые скобки для левого дочернего узла и обходим правый дочерний узел, добавляя его результат в скобках.

3⃣Объединение результатов
Собираем результаты для каждого узла, учитывая все упомянутые случаи, чтобы получить строковое представление дерева.

😎 Решение:

class Solution {
    function tree2str($t) {
        $res = "";
        $this->dfs($t, $res);
        return $res;
    }

    function dfs($t, &$res) {
        if ($t == null)
            return;
        $res .= $t->val;
        if ($t->left == null && $t->right == null)
            return;
        $res .= '(';
        $this->dfs($t->left, $res);
        $res .= ')';
        if ($t->right != null) {
            $res .= '(';
            $this->dfs($t->right, $res);
            $res .= ')';
        }
    }
}

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