剑指offer第十八题。

题目描述

image

解题思路

我们或许还记得递归的终极思想是数学归纳法,我们思考递归的时候一定不要去一步一步看它执行了啥,只会更绕。我们牢牢记住,思考的方式是我们首先假设子问题都已经完美处理,我只需要处理一下最终的问题即可,子问题的处理方式与最终那个处理方式一样,但是问题规模一定要以1的进制缩小。最后给一个递归出口条件即可。

对于本题,首先假设root的左右子树已经都处理好了,即左子树自身已经镜像了,右子树自身也镜像了,那么最后一步就是交换左右子树,问题解决。所以我只需要将root.leftroot.right交换即可。下面进入递归,就是处理子问题。子问题的处理方式与root一样,只是要缩小问题规模,所以只需要考虑root.left是什么情况,root.right是什么情况即可。

我的答案

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
public class Solution {
public void Mirror(TreeNode root) {
reverseTree(root);
}

private void reverseTree(TreeNode root){
//为空则结束
if(root == null){
return;
}
//假设root两边的子树自己都已经翻转成功了,那么只需要再将左右子树互换一下就成功了
//交换root的左右子树
swap(root);

//左右子树翻转自己去处理就行了,我们规定每个子树的root都跟最终的root处理方式一样即可
reverseTree(root.left);
reverseTree(root.right);
}

private void swap(TreeNode root){
TreeNode node = null;
node = root.left;
root.left = root.right;
root.right = node;
}
}