Задача: 107. Binary Tree Level Order Traversal II
Сложность: medium

Дан корень бинарного дерева. Верните обход значений узлов снизу вверх по уровням (то есть слева направо, уровень за уровнем, от листа к корню).

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]

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

1⃣Инициализируйте список вывода levels. Длина этого списка определяет, какой уровень в данный момент обновляется. Вам следует сравнить этот уровень len(levels) с уровнем узла level, чтобы убедиться, что вы добавляете узел на правильный уровень. Если вы все еще находитесь на предыдущем уровне, добавьте новый уровень, вставив новый список в levels.

2⃣Добавьте значение узла в последний уровень в levels.

3⃣Рекурсивно обработайте дочерние узлы, если они не равны None, используя функцию helper(node.left / node.right, level + 1).

😎 Решение:

class TreeNode {
    public $val = null;
    public $left = null;
    public $right = null;

    public function __construct($value = 0, $left = null, $right = null) {
        $this->val = $value;
        $this->left = $left;
        $this->right = $right;
    }
}

class Solution {
    private $levels = [];

    private function helper($node, $level) {
        if (!$node) return;
        if (!isset($this->levels[$level])) $this->levels[$level] = [];
        array_push($this->levels[$level], $node->val);
        if ($node->left) $this->helper($node->left, $level + 1);
        if ($node->right) $this->helper($node->right, $level + 1);
    }

    public function levelOrderBottom($root) {
        $this->helper($root, 0);
        return array_reverse($this->levels);
    }
}

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