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

相关文章

来自专栏撸码那些事

【图解数据结构】 树

943
来自专栏小文博客

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

873
来自专栏计算机视觉与深度学习基础

Leetcode 114 Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place. For example, Given...

1848
来自专栏desperate633

LintCode 中序遍历和后序遍历树构造二叉树题目代码

641
来自专栏Android机动车

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

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

982
来自专栏猿人谷

根据前序和中序推出后序

最近面试总遇到这种根据给出的两类序遍历,然后求按另一种形式序的遍历。看来有必要好好总结下这个知识点,省的每次笔试时都得花不少时间推导。 首先,我们看看前序、中序...

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

浅谈图的深度优先遍历

1449
来自专栏用户画像

4.5.2 平衡二叉树

为了避免树的高度增长过快,降低二叉排序树的性能,我们规定在插入和删除二叉树结点时,要保证任意结点的左、右子树高度差的绝对值不超过1,将这样的二叉树称为平衡二叉树...

772
来自专栏用户画像

4.3.2 线索二叉树

二叉树结点的各种遍历序列,其实质是对一个非线性结构进行线性化操作,使在这个访问序列中每一个结点(除第一个和最后一个)都有一个直接前驱和直接后继。

842
来自专栏机器学习从入门到成神

数据结构之树、森林和二叉树的转换

树转换为二叉树 (1)加线。在所有兄弟结点之间加一条连线。 (2)去线。树中的每个结点,只保留它与第一个孩子结点的连线,删除它与其它孩子结点之间的连线。...

872

扫码关注云+社区