数据结构与算法--解决问题的方法- 二叉树的的镜像

63 阅读 0 评论 42 点赞

我是靠谱客的博主舒心往事，最近开发中收集的这篇文章主要介绍数据结构与算法--解决问题的方法- 二叉树的的镜像，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

解决问题的思路

工作中遇到的问题可能用到的数据结构由很多，并且各种数据结构都不简单，我们不可能光凭借想象就能得到问题的解法，因此画图是在家具问题过程中用来帮助自己分析，推理的常用手段。很多问题比较抽象，不容易找到解决方案。我们可以借助图形帮助自己观察思考。
很多比较复杂的数据结构相关的问题，例如，二叉树，二维数组，矩阵，链表，图等问题。都可以采用画图的方式来分析。
利用图像来分析更能够直观的找到问题的解决方案，而且有时候在图中也能看出边界条件，我们可以将问题的某一种情况来代替全量，得出边界条件需要满足的值。这样编码会变得更加容易

二叉树的的镜像

题目：完成一个函数，输入一个二叉树，改函数输出他的镜像。
二叉树节点定义还是使用前面二叉树实现原理中的节点定义。
树的镜像这种问题比较新颖，光靠想的话简单情况可以想出来，当未必能一下子得出具体的实现方案。我们可以画出一个镜像图如下：

在这里插入图片描述

我们可以从上图中直观的看出镜像前后的变化，镜像前后根节点是不变化的，但是左右子树的位置交换了位置，我们可以一步一步的来话题分析，如下第一步骤。
框中的第一个子树部分的镜像信息，根节点不变，子树左右交换，交换后我们可以用同样的逻辑处理 8-9-2 子树和其他的子树，明显这部分用递归可以实现。
综上分析得出：
- 我们先前序遍历这颗树的每个节点
- 如果遍历到的节点有子节点，就交换两个子节点
- 当交换完所有非叶子节点的左右子节点后，就完成了镜像的输出。
代码实现如下：

/**
 * 获取二叉树的镜像
 * @author liaojiamin
 * @Date:Created in 17:36 2021/3/31
 */
public class MirrorBinaryTree {

    public static BinaryNode mirrorTree(BinaryNode root){
        if(root == null || (root.getLeft() == null && root.getRight() == null)){
            return root;
        }
        BinaryNode treeTemp = root.getRight();
        root.setRight(root.getLeft());
        root.setLeft(treeTemp);
        if(root.getRight() != null){
            mirrorTree(root.getRight());
        }
        if(root.getLeft() != null){
            mirrorTree(root.getLeft());
        }
        return root;
    }

    public static void main(String[] args) {
        BinaryNode node = new BinaryNode(null, null, null);
        BinarySearchTree tree1 = new BinarySearchTree();
        Random random = new Random();
        for (int i = 0; i < 20; i++) {
            node = tree1.insert(random.nextInt(100), node);
        }
        tree1.printTree(node);
        System.out.println("----------------------mirror------------");
        mirrorTree(node);
        tree1.printTree(node);
    }
}