题目描述
解题思路
先序遍历这个树的根结点,如果根结点有左右子结点,那么就交换,当交换完成所有的非叶子结点,那么就是我们所要求的镜像。
我们可以看这个示意图,从图 1 到图 4 就是一个镜像的过程,根据上面说的我们先交换根结点的左右子结点,交换后对于 2,3 这两个子结点来说,它们的子结点的顺序其实并没有改变,所以仍需继续交换对应的子结点,以此类推就是一个递归的形式了。
代码实现
public class Problem18 {
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public void Mirror(TreeNode pRoot) {
if((pRoot == null) || (pRoot.left == null && pRoot.right == null)){
return ;
}
TreeNode temp = null;
temp = pRoot.right;
pRoot.right = pRoot.left;
pRoot.left = temp;
if(pRoot.left != null){
Mirror(pRoot.left);
}
if(pRoot.right != null){
Mirror(pRoot.right);
}
}
}