剑指offer No.18 二叉树的镜像

week

发布于 2022-11-26 03:10:25

27100

代码可运行

运行总次数：0

代码可运行

https://www.nowcoder.com/practice/564f4c26aa584921bc75623e48ca3011?tpId=13&tqId=11171&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述

操作给定的二叉树，将其变换为源二叉树的镜像。

输入描述:

二叉树的镜像定义：源二叉树 
    	    8
    	   /  \
    	  6   10
    	 / \  / \
    	5  7 9 11
    	镜像二叉树
    	    8
    	   /  \
    	  10   6
    	 / \  / \
    	11 9 7  5

树的镜像对很多人来说是一个新的概念，我们未必能够一下子想出求树的镜像的方法。为了能够形成直观的印象，我们可以自己画一棵二叉树，然后根据照镜子的经验画出它的镜像。如图4.1中右边的二叉树就是左边的树的镜像。

图4.1 两棵互为镜像的二叉树

仔细分析这两棵树的特点，看看能不能总结出求镜像的步骤。这两棵树的根结点相同，但它们的左右两个子结点交换了位置。因此我们不妨先在树中交换根结点的两个子结点，就得到图4.2中的第二棵树。

交换根结点的两个子结点之后，我们注意到值为 10、6 的结点的子结点仍然保持不变，因此我们还需要交换这两个结点的左右子结点。交换之后的结果分别是图4.2 中的第三棵树和第四棵树。做完这两次交换之后，我们已经遍历完所有的非叶子结点。此时变换之后的树刚好就是原始树的镜像。

图4.2 求二叉树镜像的过程注：（a）交换根结点的左右子树；（b）交换值为10的结点的左右子结点；（c）交换值为6的结点的左右子结点。总结上面的过程，我们得出求一棵树的镜像的过程：我们先前序遍历这棵树的每个结点，如果遍历到的结点有子结点，就交换它的两个子结点。当交换完所有非叶子结点的左右子结点之后，就得到了树的镜像。

想清楚了这个思路，我们就可以动手写代码了。参考代码如下：

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public void Mirror(TreeNode root) {
        if(root!=null){
            TreeNode t=root.left;
            root.left = root.right;
            root.right = t;
            Mirror(root.left);
            Mirror(root.right);
        }
    }
}