leetcode-99-Recover-Binary-Search-Tree
题目描述（困难难度）
依旧是二分查找树的题，一个合法的二分查找树随机交换了两个数的位置，然后让我们恢复二分查找树。不能改变原来的结构，只是改变两个数的位置。二分查找树定义如下：
- 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
- 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 任意节点的左、右子树也分别为二叉查找树；
- 没有键值相等的节点。
解法一 递归
和 public void recoverTree2(TreeNode root) {
if (root == null) {
return;
}
//寻找左子树中最大的节点
TreeNode maxLeft = getMaxOfBST(root.left);
//寻找右子树中最小的节点
TreeNode minRight = getMinOfBST(root.right);
if (minRight != null && maxLeft != null) {
//左边的大于根节点，右边的小于根节点，对应情况 3，左右子树中的两个数字交换
if ( maxLeft.val > root.val && minRight.val < root.val) {
int temp = minRight.val;
minRight.val = maxLeft.val;
maxLeft.val = temp;
}
}
if (maxLeft != null) {
//左边最大的大于根节点，对应情况 1，根节点和左子树的某个数做了交换
if (maxLeft.val > root.val) {
int temp = maxLeft.val;
maxLeft.val = root.val;
root.val = temp;
}
}
if (minRight != null) {
//右边最小的小于根节点，对应情况 2，根节点和右子树的某个数做了交换
if (minRight.val < root.val) {
int temp = minRight.val;
minRight.val = root.val;
root.val = temp;
}
}
//对应情况 4，左子树中的两个数进行了交换
recoverTree(root.left);
//对应情况 5，右子树中的两个数进行了交换
recoverTree(root.right);
}
//寻找树中最小的节点
private TreeNode getMinOfBST(TreeNode root) {
if (root == null) {
return null;
}
TreeNode minLeft = getMinOfBST(root.left);
TreeNode minRight = getMinOfBST(root.right);
TreeNode min = root;
if (minLeft != null && min.val > minLeft.val) {
min = minLeft;
}
if (minRight != null && min.val > minRight.val) {
min = minRight;
}
return min;
}
//寻找树中最大的节点
private TreeNode getMaxOfBST(TreeNode root) {
if (root == null) {
return null;
}
TreeNode maxLeft = getMaxOfBST(root.left);
TreeNode maxRight = getMaxOfBST(root.right);
TreeNode max = root;
if (maxLeft != null && max.val < maxLeft.val) {
max = maxLeft;
}
if (maxRight != null && max.val < maxRight.val) {
max = maxRight;
}
return max;
}
参考 “>98 题，我们判断是否是一个合法的二分查找树是使用到了中序遍历。原因就是二分查找树的一个性质，左孩子小于根节点，根节点小于右孩子。所以做一次中序遍历，产生的序列就是从小到大排列的有序序列。 回到这道题，题目交换了两个数字，其实就是在有序序列中交换了两个数字。而我们只需要把它还原。 交换的位置的话就是两种情况。 [ 1 2 3 4 5 ] 中 2 和 3 进行交换，[ 1 3 2 4 5 ]，这样的话只产生一组逆序的数字（正常情况是从小到大排序，交换后产生了从大到小），3 2。 我们只需要遍历数组，找到后，把这一组的两个数字进行交换即可。 不相邻的两个数字交换 [ 1 2 3 4 5 ] 中 2 和 5 进行交换，[ 1 5 3 4 2 ]，这样的话其实就是产生了两组逆序的数字对。5 3 和 4 2。 所以我们只需要遍历数组，然后找到这两组逆序对，然后把第一组前一个数字和第二组后一个数字进行交换即完成了还原。 所以在中序遍历中，只需要利用一个 pre 节点和当前节点比较，如果 pre 节点的值大于当前节点的值，那么就是我们要找的逆序的数字。分别用两个指针 first 和 second 保存即可。如果找到第二组逆序的数字，我们就把 second 更新为当前节点。最后把 first 和 second 两个的数字交换即可。解法二
看完两件小事
如果你觉得这篇文章对你挺有启发，我想请你帮我两个小忙：
- 把这篇文章分享给你的朋友 / 交流群，让更多的人看到，一起进步，一起成长！
- 关注公众号 「方志朋」，公众号后台回复「666」 免费领取我精心整理的进阶资源教程
本文著作权归作者所有，如若转载，请注明出处
转载请注明：文章转载自「 Java极客技术学习 」https://www.javajike.com
微信扫一扫 
admin