描述

操作给定的二叉树，将其变成源二叉树的镜像。【即左右子节点互换】

1
2
3
4
5
6
7
8
9
10
11
12
二叉树的镜像定义：源二叉树 
    	    8
    	   /  \
    	  6   10
    	 / \  / \
    	5  7 9 11
    	镜像二叉树
    	    8
    	   /  \
    	  10   6
    	 / \  / \
    	11 9 7  5

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class TreeNode{
    var $val;
    var $left = NULL;
    var $right = NULL;
    function __construct($val){
        $this->val = $val;
    }
}

$a1 = new TreeNode(8);
$a2 = new TreeNode(6);
$a3 = new TreeNode(10);
$a1->left = $a2;
$a1->right = $a3;
$a4 = new TreeNode(5);
$a5 = new TreeNode(7);
$a2->left = $a4;
$a2->right = $a5;
$a6 = new TreeNode(9);
$a7 = new TreeNode(11);
$a3->left = $a6;
$a3->right = $a7;

// 方法1：递归循环
function Mirror(&$root)
{
    if(is_null($root)){
        return null;
    }
    $temp = $root->left;
    $root->left = $root->right;
    $root->right = $temp;
    if(!is_null($root->left)){
        Mirror($root->left);
    }
    if(!is_null($root->right)){
        Mirror($root->right);
    }
}

// 方法2：模拟队列
// 思路：通过`array_push`和`array_shift`模拟一个栈；循环处理这个队列直到队列中没有数据
function Mirror(&$root)
{
    $temp = array();
    array_push($temp,$root);
    while(!empty($temp)){
        $data = array_shift($temp);
        $temp_left = $data->left;
        $data->left = $data->right;
        $data->right = $temp_left;
        if(!is_null($data->left)){
            array_push($temp,$data->left);
        }
        if(!is_null($data->right)){
            array_push($temp,$data->right);
        }
    }
    return $root;
}