《剑指Offer》-27.二叉树的镜像

题干

请完成一个函数，输入一棵二叉树，该函数输出它的镜像。二叉树节点的定义如下：

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
}

解题思路

输入二叉树

graph TD
8-->6
8-->10
6-->5
6-->7
10-->9
10-->11

输出二叉树

graph TD
8-->10
8-->6
10-->11
10-->9
6-->7
6-->5

从图中可以分析出，输出的镜像二叉树和原二叉树的各个子树的根节点相同，子节点交换了位置，因为我们只需要将各个节点的左右孩子交换即可得到镜像。

代码实现

<?php

class TreeNode
{
    private $val;
    private $left;
    private $right;

    public function __set($name, $value)
    {
        $this->$name = $value;
    }

    public function __get($name)
    {
        return $this->$name;
    }
}

function getTree()
{
    $node1 = new TreeNode();
    $node1->val = 8;
    $node2 = new TreeNode();
    $node2->val = 6;
    $node3 = new TreeNode();
    $node3->val = 10;
    $node1->left = $node2;
    $node1->right = $node3;
    $node4 = new TreeNode();
    $node4->val = 5;
    $node5 = new TreeNode();
    $node5->val = 7;
    $node2->left = $node4;
    $node2->right = $node5;
    $node6 = new TreeNode();
    $node6->val = 9;
    $node7 = new TreeNode();
    $node7->val = 11;
    $node3->left = $node6;
    $node3->right = $node7;

    return $node1;
}

function mirror(&$tree)
{
    if ($tree != null) {
        $tmp = $tree->left;
        $tree->left = $tree->right;
        $tree->right = $tmp;
        if ($tree->left!=null) {
            mirror($tree->left);
        }
        if ($tree->right!=null){
            mirror($tree->right);
        }
    }
}

$tree = getTree();
mirror($tree);
var_dump($tree);