给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树
思路：
1. 利用二叉搜索树 中序遍历结果是升序的特点找到错误逆序对
2. 交换两个错误节点
复杂度分析：
时间复杂度: O(n) 因为只有一个中序遍历
空间复杂度: O(n) ， 二叉树的空间复杂度就是树的高度， 普通情况是O(H)，但是最坏情况所有结点都在一侧时高度就等于结点数 H = N
寻找错误逆序对核心逻辑.png
/**
思路：
1.利用二叉搜索树中序遍历的结果是升序的特点找出错误逆序对
2.交换两个错误结点
时间复杂度:O(n)
空间复杂度:O(n)
*/
class Solution1 {
TreeNode prev;//前置结点
TreeNode first;//第一个错误结点
TreeNode second;//第二个错误结点
public void recoverTree(TreeNode root) {
//1.寻找错误结点
findWeongNodes(root);
//2.恢复错误结点
int tmp = first.val;
first.val = second.val;
second.val = tmp;
}
//递归 中序遍历寻找错误结点
private void findWeongNodes(TreeNode root){
//0.递归退出条件
if(root==null) return;
//1.搜索左边
findWeongNodes(root.left);
//2.当前结点是否是错误结点
if(prev != null && prev.val > root.val) {//前置结点不为空 且 前置结点的值 大于 当前结点
//第二个错误结点：最后一个逆序对中较小的结点
second = root;
if(first!=null) return;//first不为空说明已经找到了第一个错误结点(第一个逆序对中较大的结点)
//来到这里说明还没找到第一个错误结点，那么prev就是这个结点
first = prev;
}
prev = root;//重点：保留当前结点，成为下一次遍历的前置结点
//3.搜索右边
findWeongNodes(root.right);
}
}
执行结果.png
进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？
思路：使用二叉树的Morris遍历，也叫线索二叉树 可以实现时间复杂度O(n) 空间复杂度O(1)
执行步骤.png
/**
时间复杂度: O(n) 实际上是O(2n) 因为一个结点会走两次
空间复杂度: O(1)
*/
class Solution {
public TreeNode prev;
public TreeNode first;
public TreeNode second;
//根据中序遍历升序的规律找到错误节点
private void findNode(TreeNode root) {
//结束条件
if(root==null) return;
//前一个节点不为空 且val的值大于当前节点的val值
if(prev != null && prev.val > root.val) {
//第二个错误节点: 最后一个逆序对中较小的那个节点
second = root;
//first不为空说明已经获得了第一个错误节点:第一个逆序对中较大的那个节点
if(first != null) return;
first = prev;
}
//保留当前节点的成为下次遍历的前一个节点
prev = root;
}
public void recoverTree(TreeNode root) {
//1. Morris遍历
TreeNode node = root;
while(node != null) {
//1.1 左子树不为空
if(node.left != null) {
//找到前驱节点条件 向右走没有新的节点了 且 遇到的不是自己
TreeNode pred = node.left;
while(pred.right != null && pred.right != node) {
pred = pred.right;
}
//前驱节点的右子树为空，修改其right指向自己
if(pred.right == null) {
pred.right = node;
node = node.left;
}else {//前驱节点的右子树不为空，就清空 因为此时已经走回来了 此时pred.right = node
findNode(node);
pred.right = null;
node = node.right;//向右搜索
}
}else {//1.2 没有左子树了 说明到最左边了 然后往回走
findNode(node);
node = node.right;
}
}
//2. 交换两个错误节点
int tmp = first.val;
first.val = second.val;
second.val = tmp;
}
}
执行结果.png
网友评论