在PHP中实现二叉树的倒置
在PHP中实现二叉树的倒置
提问于 2018-08-23 03:45:57
伙计们，我在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));回答 2
Stack Overflow用户
发布于 2018-08-23 04:59:22
您可以使用递归函数来完成此操作。我记得几年前做过这样的练习...嗯，我的解决方案是这样的：
$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
Stack Overflow用户
发布于 2019-01-10 08:22:16
function invertTree($root) {
if($root == null)
return null;
$flag = $root->right;
$root->right = invertTree($root->left);
$root->left = invertTree($flag);
return $root;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/51974104
复制相关文章
相似问题