Инвертировать двоичное дерево в переполнении стека

Question

Инвертировать двоичное дерево в переполнении стека

ребята, у меня есть эта проблема в PHP Я пытаюсь инвертировать двоичное дерево в PHP, но я не знаю, как решить эту проблему.

Задача состоит в том, чтобы инвертировать двоичное дерево, чтобы порядок листьев был инвертирован.

Пример:

превращается в:

Примечание: имейте в виду, что дерево также может быть несбалансированным.

/**
* 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));

2

binary invert php tree

Решение

Другие решения

function invertTree($root) {

if($root == null)
return null;
$flag = $root->right;
$root->right = invertTree($root->left);
$root->left = invertTree($flag);
return $root;
}

0

Источник

Accepted Answer

Вы можете сделать это, используя рекурсивную функцию … Я помню, как выполнял это упражнение много лет назад … Ну, мое решение было бы примерно таким:

$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

0