剑指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 条评论
登录 后参与评论

相关文章

来自专栏向治洪

数据结构之二叉树

二叉树的定义: 二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及...

1875
来自专栏小文博客

小文’s blog — 平衡二叉树构造方法

873
来自专栏撸码那些事

【图解数据结构】 树

893
来自专栏章鱼的慢慢技术路

笔试常考题型之二叉树的遍历

1624
来自专栏大闲人柴毛毛

剑指 offer代码解析——面试题39二叉树的深度

题目:输入一颗二叉树的根结点,求该树的深度。从根结点到叶结点一次经过的结点形成树的一条路径,最长路径的长度为树的深度。 分析:本题是一道典型的“分治法”。要...

2725
来自专栏Android机动车

数据结构——二叉树的定义和性质

在一些电视节目中,会猜测商品价格,有的人是一点一点的数字累加,这样的策略效率太低了。其实有一种经典的折半查找算法,就类似于我们今天要说的二叉树。

952
来自专栏WindCoder

二叉树的动态链式存储实现—C语言

311
来自专栏猿人谷

判断二叉树是不是平衡

平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超...

1826
来自专栏恰同学骚年

剑指Offer面试题:5.重建二叉树

  在二叉树的前序遍历序列中,第一个数字总是树的根结点的值。但在中序遍历序列中,根结点的值在序列的中间,左子树的结点的值位于根结点的值的左边,而右子树的结点的值...

794
来自专栏用户画像

4.3.1 二叉树的遍历

所谓二叉树的遍历,是指按照某条搜索路径访问树中的每个结点,使得每个几点均被访问一次,而且仅被访问一次。

662

扫描关注云+社区