在PHP中反转二叉树

Question

大家好，我有一个与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));

- Osmair Coelho

---

您的二叉树类有一个反转方法，它是否不能正常工作？它具体是做什么的？ - Don't Panic

欢迎来到SO，并提出了一个好问题。请注意，您的“invert”函数在叶子节点上返回“null”，但这是不被您的返回类型所允许的，因此请考虑修复以编译--如果您删除返回类型说明符，您的代码将产生所需的输出。 - ggorlen

欢迎来到SO，请测试答案并与您的问题互动。 :) - Rafael

谢谢大家，我去掉了反转调用，现在它完美地工作了。 - Osmair Coelho

Answer 1

你可以使用递归函数来完成它…我记得几年前做过这样的练习…好吧，我的解决方案大致如下：

$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

- Rafael

---

谢谢你，Rafael，分享这个问题，我解决了，感谢你的时间。 - Osmair Coelho

如果您使用了这个答案，请点赞并将问题标记为已解决。 :) - Rafael

Answer 2

function invertTree($root) {

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

- Tarek Mahfouz