Задача: 776. Split BST
Дан корень бинарного дерева поиска (BST) и целое число target, разделите дерево на два поддерева, где первое поддерево содержит узлы, которые меньше или равны значению target, а второе поддерево содержит узлы, которые больше значения target. Не обязательно, чтобы дерево содержало узел со значением target.
Кроме того, большая часть структуры исходного дерева должна сохраниться. Формально, для любого потомка c с родителем p в исходном дереве, если они оба находятся в одном поддереве после разделения, то узел c все еще должен иметь родителя p.
Верните массив из двух корней двух поддеревьев в порядке.
Пример:
Input: root = [4,2,6,1,3,5,7], target = 2
Output: [[2,1],[4,3,6,null,null,5,7]]
👨💻 Алгоритм:
1⃣Базовый случай: Если корень равен null, верните массив, содержащий два указателя null. Это необходимо для обработки случая, когда дерево пустое.
2⃣Проверьте, больше ли значение корня целевого значения. Если да, рекурсивно разделите левое поддерево, вызвав splitBST(root->left, target). Прикрепите правую часть разделенного к левому поддереву корня. Верните массив, содержащий левую часть разделенного и текущий корень.
3⃣Если значение корня меньше или равно целевому значению, рекурсивно разделите правое поддерево, вызвав splitBST(root->right, target). Прикрепите левую часть разделенного к правому поддереву корня. Верните массив, содержащий левую часть разделенного и текущий корень.
😎 Решение:
class TreeNode {
public $val;
public $left;
public $right;
function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
class Solution {
function splitBST($root, $target) {
if ($root === null) {
return [null, null];
}
if ($root->val > $target) {
list($left, $right) = $this->splitBST($root->left, $target);
$root->left = $right;
return [$left, $root];
} else {
list($left, $right) = $this->splitBST($root->right, $target);
$root->right = $left;
return [$root, $right];
}
}
}👉Новости 👉База вопросов