Инвертировать двоичное дерево в PHP
ребята, у меня эта проблема в PHP. Я пытаюсь инвертировать двоичное дерево в PHP, но я не знаю, как решить эту проблему.
Задача состоит в том, чтобы инвертировать двоичное дерево, чтобы порядок листьев был инвертирован.
Пример:
1
/ \
2 3
/ \ / \
4 5 6 7
инвертирует в:
1
/ \
3 2
/ \ / \
7 6 5 4
Примечание: имейте в виду, что дерево также может быть разбалансировано.
/**
* leaf data structure
*/
class BinaryNode {
/** @var mixed null */
public $value = null;
/** @var BinaryNode null */
public $left = null;
/** @var BinaryNode null */
public $right = null;
/**
* @param mixed $value
*/
public function __construct( $value ) {
$this->value = $value;
}
}
class BinaryTree
{
/**
* @param BinaryNode $root
* @return BinaryNode
*/
public static function invert($root): BinaryNode
{
//$BinaryNode = new BinaryNode();
if (!isset($root)) return $root;
$tempLeftNode = $root->left;
$root->left = $root->right;
$root->right = $tempLeftNode;
self::invert($root->left);
self::invert($root->right);
return $root;
}
}
$root = new BinaryNode(1);
$root->left = new BinaryNode(2);
$root->right = new BinaryNode(3);
$root->left->left = new BinaryNode(4);
$root->left->right = new BinaryNode(5);
$root->right->left = new BinaryNode(6);
$root->right->right = new BinaryNode(7);
print_r(BinaryTree::invert($root));
Добро пожаловать в SO и хороший вопрос. Просто обратите внимание, что ваша функция invert возвращает null на листьях, но это запрещено вашим типом возврата, поэтому подумайте о том, чтобы исправить это для компиляции - если вы удалите спецификатор типа возврата, ваш код выдаст желаемый результат.
Добро пожаловать в SO и проверьте ответ. Взаимодействуйте со своим вопросом. :)
Спасибо, ребята, я удалил обратный вызов, и теперь он отлично работает
Ответы 2
Вы можете сделать это с помощью рекурсивной функции ... Я помню, как делал подобное упражнение много лет назад ... Что ж, мое решение было бы примерно таким:
$array = [
'a' => [
'b1' => [
'c1' => [
'e1' => 4,
'f1' => 5,
'g1' => 6,
],
'd1' => [
'e11' => 4,
'f11' => 5,
'g11' => 6,
]
],
'b2' => [
'c2' => [
'e2' => 4,
'f2' => 5,
'g2' => 6,
],
'd2' => [
'e21' => 4,
'f21' => 5,
'g21' => 6,
]
],
]
];
С функцией:
function reverse_recursively($arrayInput) {
foreach ($arrayInput as $key => $input) {
if (is_array($input)) {
$arrayInput[$key] = reverse_recursively($input);
}
}
return array_reverse($arrayInput);
}
echo '<pre>';
print_r($array);
echo '<br>';
print_r(reverse_recursively($array));
И вы можете увидеть тест здесь: https://3v4l.org/2pYhR
Спасибо, Рафаэль, что поделился, я решил эту проблему, ценю ваше время
Если вы использовали этот ответ, проголосуйте за и отметьте вопрос как ответ. :)
function invertTree($root) {
if ($root == null)
return null;
$flag = $root->right;
$root->right = invertTree($root->left);
$root->left = invertTree($flag);
return $root;
}
В вашем классе BinaryTree есть метод инвертирования. Это не работает должным образом? Что оно делает?