Сложность: medium
Дан корень бинарного дерева, соберите узлы дерева следующим образом:
Соберите все листовые узлы.
Удалите все листовые узлы.
Повторяйте, пока дерево не станет пустым.
Пример:
Input: root = [1,2,3,4,5]
Output: [[4,5,3],[2],[1]]
Explanation:
[[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.
👨💻 Алгоритм:
1⃣Реализовать функцию getHeight(node), которая будет вычислять высоту каждого узла в дереве с использованием рекурсивного обхода в глубину (post-order). Если узел является null, вернуть -1.
2⃣Сохранить пары (высота, значение) для всех узлов и отсортировать их по высоте.
3⃣Организовать узлы по высоте и вернуть результат.
😎 Решение:
class Solution {
private $pairs = [];
private function getHeight($node) {
if ($node === null) return -1;
$leftHeight = $this->getHeight($node->left);
$rightHeight = $this->getHeight($node->right);
$currHeight = max($leftHeight, $rightHeight) + 1;
$this->pairs[] = [$currHeight, $node->val];
return $currHeight;
}
public function findLeaves($root) {
$this->getHeight($root);
usort($this->pairs, function($a, $b) {
return $a[0] <=> $b[0];
});
$solution = [];
$currentHeight = -1;
foreach ($this->pairs as $pair) {
if ($pair[0] !== $currentHeight) {
$solution[] = [];
$currentHeight = $pair[0];
}
$solution[count($solution) - 1][] = $pair[1];
}
return $solution;
}
}Ставь 👍 и забирай 📚 Базу знаний