剑指offer代码解析——面试题19二叉树的镜像

   分析:所谓“镜像”就是从镜子里看到的样子。我们可以画一棵二叉树,然后画出该二叉树的镜像。画完图之后我们会发现,所谓“二叉树的镜像”就是把二叉树中所有子树的左孩子和右孩子进行交换。因此需要遍历二叉树所有的结点,在遍历的同时交换非叶子结点的左右子树。遍历我们可以使用先序遍历,首先判断当前根结点是否为叶子结点,若非叶子结点,则交换左右孩子,然后再分别对左右孩子进行相同的操作。

   首先,我们需要构造二叉树的结点类,一个结点中包含一个数据域data、一个左孩子left、一个右孩子right,代码如下:

/**
 * 二叉树的结点
 */
class BinaryTreeNode<T>{
	T data;//结点的数据域
	BinaryTreeNode<T> left;//左子树
	BinaryTreeNode<T> right;//右子树
}

下面开始编写镜像函数:

/**
	 * 二叉树镜像函数
	 * @param root 输入二叉树的根结点
	 */
	public static <T> void binaryTreeMirror(BinaryTreeNode<T> root){
		//若二叉树为空
		if(root==null)
			return;
		
		//若二叉树只有一个结点
		if(root.left==null && root.right==null)
			return;
		
		//若二叉树为有孩子结点,则交换左右子树
		{
			//交换左右子树
			BinaryTreeNode<T> temp = root.left;
			root.left = root.right;
			root.right = temp;
		}
		
		//分别对左右重复上述操作
		{
			if(root.left!=null)
				binaryTreeMirror(root.left);
			if(root.right!=null)
				binaryTreeMirror(root.right);
		}
	}

为了能够对上述算法进行测试,我编写了一个二叉树的中序遍历函数,我们可以比较二叉树镜像前和镜像后的中序遍历结果来判断算法是否正确。二叉树中序遍历函数如下:

<span style="white-space:pre">	</span>/**
	 * 二叉树的中序遍历
	 * @param root 输入的二叉树的根
	 */
	public static <T> void preOrder(BinaryTreeNode<T> root){
		//若当前二叉树为空
		if(root==null)
			return;
		
		//中序遍历二叉树
		{
			preOrder(root.left);//中序遍历左子树
			System.out.print(root.data+",");//访问根结点
			preOrder(root.right);//中序遍历右子树
		}
	}

一切准备工作就绪,下面就开始测试我们的算法吧。

我创建了一棵四个结点的二叉树,并且所有结点均是左孩子。那么经过镜像后该二叉树的所有结点应该都是右孩子。并且前后两棵树的中序遍历正好是逆序关系。

	public static void main(String[] args){
		BinaryTreeNode<Integer> root = new BinaryTreeNode<Integer>();
		BinaryTreeNode<Integer> root1 = new BinaryTreeNode<Integer>();
		BinaryTreeNode<Integer> root2 = new BinaryTreeNode<Integer>();
		BinaryTreeNode<Integer> root3 = new BinaryTreeNode<Integer>();
		root.data = 0;
		root1.data = 1;
		root2.data = 2;
		root3.data = 3;
		root.left = root1;
		root1.left = root2;
		root2.left = root3;
		
		System.out.println("镜像前:");
		preOrder(root);
		System.out.println("镜像后:");
		binaryTreeMirror(root);
		preOrder(root);
		
	}

输出结果为:

镜像前:3,2,1,0

镜像后:0,1,2,3

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏木宛城主

SharePoint 2013 Backup Farm Automatically With a Powershell and Windows Task Schedule

In this post,I will show you SharePoint 2013 How to Backup Farm Automatically w...

1847
来自专栏依乐祝

[译]ASP.NET Core Web API 中使用Oracle数据库和Dapper看这篇就够了

文章地址: https://www.cnblogs.com/yilezhu/p/9276565.html

901
来自专栏技术小黑屋

Issues About Installing Octopress

Actually I am fresh to Write Blog with Octopress in Github Pages.According to th...

912
来自专栏算法修养

CodeForces 709C Letters Cyclic Shift

C. Letters Cyclic Shift time limit per test 1 second memory limit per test ...

2806
来自专栏Golang语言社区

golang把文件复制到另一个目录

//本程序 主要功能是把A文件夹下的文件与B目录下文件对比,如果找到就覆盖到B相应的目录下。 // 用法: merge A目录 B目录 // merge....

35212
来自专栏james大数据架构

常见的几种Flume日志收集场景实战

  这里主要介绍几种常见的日志的source来源,包括监控文件型,监控文件内容增量,TCP和HTTP。 Spool类型   用于监控指定目录内数据变更,若有新文...

2605
来自专栏Java学习123

转 svn: E170001报错的原因以及解决方案

3557
来自专栏尚国

S2-057远程代码执行漏洞复现过程

https://github.com/vulhub/vulhub/tree/master/struts2/s2-048

2033
来自专栏晓晨的专栏

Entity Framework Core 2.0 使用入门

1493
来自专栏康怀帅的专栏

Apache 配置

本文简要介绍了 Apache 配置 https 、子域名。 如果启动出现错误,搜索一下错误信息,一般启用某些模块就行了。 https 修改主配置文件 /usr/...

3595

扫码关注云+社区