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

相关文章

来自专栏琯琯博客

PHP二叉树(一):平衡二叉树(AVL)

平衡二叉树 <?php /** * description: 平衡二叉树 */ //结点 class Node { public $key; ...

39590
来自专栏weixuqin 的专栏

数据结构学习笔记(树、二叉树)

27330
来自专栏xingoo, 一个梦想做发明家的程序员

二叉排序树的删除操作

算法思想 二叉排序树,删除操作主要针对三种情况。 1 叶子节点-直接删除就可以了 2 没有左孩子的节点-直接嫁接右子树就可以了(没有右孩子的节点-直接嫁接左子树...

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

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

19240
来自专栏Android相关

平衡二叉树

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

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

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

18850
来自专栏用户画像

4.3.1 二叉树的遍历

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

9420
来自专栏Hongten

ArrayList VS Vector(ArrayList和Vector的区别)_面试的时候经常出现

1.4K20
来自专栏WindCoder

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

36210
来自专栏海天一树

二叉树的建立和遍历

二叉树:每个结点的子结点个数不大于2的树,叫做二叉树。 根结点:最顶部的那个结点叫做根结点,根结点是所有子结点的共同祖先。比如上图中的“7”结点就是根结点。 子...

10430

扫码关注云+社区

领取腾讯云代金券