题目:

在一颗搜索二叉树中,可能有两个位置的节点错位了,用一个函数实现判断并把他们调整过来,除了调换这两个节点之外,不能破坏二叉树原有的结构。如果没有错误的节点或者错误节点数超过两个则不用调整直接返回。

难度:校

解答:

首先需要找到判断错误节点的办法,其次需要想清楚节点调换的情况。情况非常之多。

判断错误节点办法:
1,通过搜索二叉树的中根遍历,得到中根遍历的列表,看看是不是依次递增的,如果是,说明没有错,直接返回头节点。如果不是进入第二步。
2,怎样判断一个失序的中根遍历列表是只需要调整两个节点就能变好的呢?

假设现在我们得到的序列是:1,2,3,5,4,6,7
5和4错了,调整过来就对了,那么我们可以检查在这个列表中是否有一次降序的情况(5,4)就可以定位出两个错的节点。

假设我们得到的序列是:1,6,3,4,5,2,7
2和6错了,调整过来就对了。那么我们可以检查在这个列表中是否有两次降序的情况(6,3)和(5,2)

总结为,检查列表时如果有一次或两次降序的情况下,有可能定位出错误的节点。除此之外,我们都不需要处理,可以直接返回。

为什么说有可能呢?请看如下的情况:
假设我们得到的序列是:1,4,2,3,5,6,7
这个列表中4,2,3错了,如果只能调换两个节点,我们无法把顺序改正确,但是在列表中只有一次降序的情况(4,2)。

所以我们需要先按照上面提到的可能的方法,找到两个错误节点,然后看看这两个节点在列表中调换后,列表是否恢复递增,如果恢复,我们可以确定找到的两个节点有效,调换过来就可以符合要求了;如果不能恢复,则我们可以确定,错误节点的数量超过了两个,直接返回即可。

如果按照上文的方法你找到了两个节点,而没有返回,说明你可以进行如下的思考了,如何在树中调整两个节点的位置?
一种比较简单的办法是这样的:

BinaryTreeNode firstErr = 你找到的第一个错误的节点
BinaryTreeNode secondErr = 你找到的第二个错误的节点
int tmp = secondErr.value;
secondErr.value = firstErr.value;
firstErr.value = tmp;

即直接把两个节点的值替换的方法,如果能这么做当然很好,省去了很多的麻烦。但这种方式有很大的局限,要求节点的数据项相对简单,同时有赋值权限才可以这么做。
本题考察的重点并不是这个,而是对节点调换时,边界处理的全面考虑。

怎么做呢,其实粗起来比较简单,就是把两个节点从各自的“周围环境”中挖出,调换位置后,再恢复与“周围环境”的联系。这个“周围环境”指各自的父节点和子节点,举个例子:

jj005-1
如上图所示,我们需要将firstErrParent指向secondErr,secondErrParent指向firstErr,同时firstErr指向secondErr的左右孩子,secondErr指向firstErr的左右孩子。
具体两个节点在树中怎么调换呢?其实粗起来比较简单,就是把两个节点从各自的“周围环境”中挖出,调换位置后,再恢复与“周围环境 ”的联系。这个“周围环境”指两个错误节点各自父节点和子节点,举个例子:

我们需要将firstErrParent指向secondErr,
secondErrParent指向firstErr,同时firstErr指向secondErr的左右孩子,secondErr指向firstErr的左右孩子。

大体上讲就是这样的,但是仔细一想实现细节,我们发现我们必须讨论如下三个问题:
问题一:
是否其中有一个是头?如果有,谁是头?
问题二:
是否两个节点挨着?如果挨着,谁是谁的父节点,子节点是父节点的左孩子还是右孩子;如果不挨着呢?
问题三:
两个节点分别是各自父节点的左孩子还是右孩子

注意:
在中根遍历序列中,firstErr是先出现的,secondErr是后出现的。
所以firstErr一定不是secondErr的右孩子;
secondErr也一定不是firstErr的左孩子。

三个问题和注意点相互影响,十分复杂,情况非常复杂,个人认为无法简化。比如如果firstErr是头节点,那么就不用在追求firstErr是firstErrParent的左孩子还是右孩子,
因为firstErrParent为null。

最终,经过细细的整理,情况有14种:
1,firstErr是头,并且firstErr是secondErr的父节点。
2,firstErr是头,但firstErr不是secondErr的父节点,second是secondParent的左孩子
3,firstErr是头,但firstErr不是secondErr的父节点,second是secondParent的右孩子
4,secondErr是头,并且secondErr是firstErr的父节点。
5,secondErr是头,但secondErr不是firstErr的父节点,first是firstParent的左孩子
6,secondErr是头,但secondErr不是firstErr的父节点,first是firstParent的右孩子
7,没有任何一个节点是头,firstErr是secondErr的父节点,first是firstParent的左孩子
8,没有任何一个节点是头,firstErr是secondErr的父节点,first是firstParent的右孩子
9,没有任何一个节点是头,secondErr是firstErr的父节点,second是secondParent的左孩子
10,没有任何一个节点是头,secondErr是firstErr的父节点,second是secondParent的右孩子
11,没有任何一个节点是头,同时谁也不是谁的父节点,first是其父的左孩子,second是其父的左孩子
12,没有任何一个节点是头,同时谁也不是谁的父节点,first是其父的左孩子,second是其父的右孩子
13,没有任何一个节点是头,同时谁也不是谁的父节点,first是其父的右孩子,second是其父的左孩子
14,没有任何一个节点是头,同时谁也不是谁的父节点,first是其父的右孩子,second是其父的右孩子

本文章原始出处”脑客爱刷题”  www.knockgate.com 版权所有,转载请标明出处!

1 条评论

欢迎留言