【剑指Offer学习】【面试题19 :二叉树的镜像】[通俗易懂]

【剑指Offer学习】【面试题19 :二叉树的镜像】

大家好,又见面了,我是全栈君。

题目:请完毕一个函数,输入一个二叉树,该函数输出它的镜像。


二叉树结点的定义:

/** * 二叉树的树结点 */
public static class BinaryTreeNode {
    int value;
    BinaryTreeNode left;
    BinaryTreeNode right;
}

解题思路:

我们先前序遍历这棵树的每一个结点。假设遍历到的结点有子结点。就交换它的两个子结点。当交换全然部非叶子结点的左右子结点之后。就得到了树的镜像。

代码实现:

public class Test19 {
    /** * 二叉树的树结点 */
    public static class BinaryTreeNode {
        int value;
        BinaryTreeNode left;
        BinaryTreeNode right;
    }

    /** * 请完毕一个函数,输入…个二叉树。该函数输出它的镜像 * * @param node 二叉树的根结点 */
    public static void mirror(BinaryTreeNode node) {
        // 假设当前结点不为空则进行操作
        if (node != null) {
            // 以下是交换结点左右两个子树
            BinaryTreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;

            // 对结点的左右两个子树进行处理
            mirror(node.left);
            mirror(node.right);
        }
    }

    public static void printTree(BinaryTreeNode node) {
        if (node != null) {
            printTree(node.left);
            System.out.print(node.value + " ");
            printTree(node.right);
        }
    }

    public static void main(String[] args) {
        // 8
        // / \
        // 6 10
        // / \ / \
        // 5 7 9 11
        BinaryTreeNode root = new BinaryTreeNode();
        root.value = 8;
        root.left = new BinaryTreeNode();
        root.left.value = 6;
        root.left.left = new BinaryTreeNode();
        root.left.left.value = 5;
        root.left.right = new BinaryTreeNode();
        root.left.right.value = 7;
        root.right = new BinaryTreeNode();
        root.right.value = 10;
        root.right.left = new BinaryTreeNode();
        root.right.left.value = 9;
        root.right.right = new BinaryTreeNode();
        root.right.right.value = 11;
        printTree(root);
        System.out.println();
        mirror(root);
        printTree(root);
        // 1
        // /
        // 3
        // /
        // 5
        // /
        // 7
        // /
        // 9
        BinaryTreeNode root2 = new BinaryTreeNode();
        root2.value = 1;
        root2.left = new BinaryTreeNode();
        root2.left.value = 3;
        root2.left.left = new BinaryTreeNode();
        root2.left.left.value = 5;
        root2.left.left.left = new BinaryTreeNode();
        root2.left.left.left.value = 7;
        root2.left.left.left.left = new BinaryTreeNode();
        root2.left.left.left.left.value = 9;
        System.out.println("\n");
        printTree(root2);
        System.out.println();
        mirror(root2);
        printTree(root2);

        // 0
        // \
        // 2
        // \
        // 4
        // \
        // 6
        // \
        // 8
        BinaryTreeNode root3 = new BinaryTreeNode();
        root3.value = 0;
        root3.right = new BinaryTreeNode();
        root3.right.value = 2;
        root3.right.right = new BinaryTreeNode();
        root3.right.right.value = 4;
        root3.right.right.right = new BinaryTreeNode();
        root3.right.right.right.value = 6;
        root3.right.right.right.right = new BinaryTreeNode();
        root3.right.right.right.right.value = 8;
        System.out.println("\n");
        printTree(root3);
        System.out.println();
        mirror(root3);
        printTree(root3);


    }
}

执行结果:

这里写图片描写叙述

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115522.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • Sublime Text 3安装及常用插件安装

    Sublime Text 3安装及常用插件安装欢迎访问我的个人博客http://xiaolongwu.cn/一、Sublime3下载1.百度搜索Sublime3download,选择进入下载页面2.我选择下载Win64位安装程序二、Sublime3安装傻瓜式安装,一直点下一步即可。三、Sublime3插件配置1.直接安装安装Sublimetext3插件很方便,可以直接下载安装…

  • CMake Error: The current CMakeCache.txt directory is different…[通俗易懂]

    CMake Error: The current CMakeCache.txt directory is different…[通俗易懂]零、问题描述开始学ROS时,需要编译别人的功能包,常常把别人的工作空间拿过来使用,但编译时会出现各种错误,如下的目录问题:CMakeError:ThecurrentCMakeCache.txtdirectory/home/vistar/desktop/catkin_ws/build/CMakeCache.txtisdifferentthanthedirectory/ho……………

    2022年10月25日
  • nested exception is java.lang.StackOverflowError解析

    背景介绍:项目是微服务的,使用docker容器,使用jenkins部署。测试环境有个公共服务一直以来都能正常发布,突然有一天不行了,经常发布失败,然后多发布几次就好了。报错如下:是栈溢出了,一般

  • LabVIEW入门教程

    LabVIEW从初学到入门LabVIEW简介如何入门LabVIEW我该去哪找相应学习资源LabVIEW简介LabVIEW是一款图形化编程语言(G语言),由美国国家仪器研制(NationalInstruments,NI)研制,被称为虚拟仪器(VirtualInstrument,VI)。它提供了整套的工具用来对信号进行采集、分析、保存及后续的处理。优点:界面美观程序模块化强与设备交…

  • RT Thread FinSH组件

    RT Thread FinSH组件FinSH入口rt_components_init();voidmain_thread_entry(void*parameter){externintmain(void);#ifdefRT_USING_COMPONENTS_INIT/*RT-Threadcomponentsinitialization*/rt_components_init();#endif/*RT_USING_COMPONENTS_INIT*/#ifdefRT_US

  • ICMP数据包分析_Wireshark数据包分析实战

    ICMP数据包分析_Wireshark数据包分析实战一.实验目的1.学习和掌握ICMP协议的基本作用和报文格式2.理解ICMP协议与IP协议的封装关系3.学习和掌握ICMP协议的应用和报文格式4.理解tracertoute工作过程二.实验拓扑三.实验工具GNS3和Wireshark抓包分析软件四.ICMP协议的封装格式(1)Type类型值,标识ICMP分组类型(2)Code代码值,标识ICMP分组类型的某一种具体分组(3)Checksum校验和,用于检验数据包是否完整或是否被修改(4)Identifier标识符,标识本进程

    2022年10月21日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号