一、题目描述
给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。
示例 1：
输入：root = [1,3,null,null,2] 输出：[3,1,null,null,2] 解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
示例 2：
输入：root = [3,1,4,null,null,2] 输出：[2,1,4,null,null,3] 解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
提示：
- 树上节点的数目在范围
[2, 1000]内 -2^31 <= Node.val <= 2^31 - 1
二、解题思路
- 二叉搜索树的中序遍历是升序的，如果有两个节点被错误交换，那么在中序遍历的结果中，会出现一个逆序对，或者两个逆序对。
- 使用中序遍历二叉搜索树，找到逆序对的位置，记录下逆序对中的两个节点。
- 交换这两个节点的值，恢复二叉搜索树。
三、具体代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private TreeNode prev = null;
private TreeNode first = null;
private TreeNode second = null;
public void recoverTree(TreeNode root) {
inorderTraversal(root);
if (first != null && second != null) {
int temp = first.val;
first.val = second.val;
second.val = temp;
}
}
private void inorderTraversal(TreeNode node) {
if (node == null) {
return;
}
inorderTraversal(node.left);
if (prev != null && prev.val > node.val) {
if (first == null) {
first = prev;
}
second = node;
}
prev = node;
inorderTraversal(node.right);
}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
- 中序遍历二叉树的时间复杂度是 O(n)，其中 n 是树中节点的数量。因为每个节点都会被访问一次。
- 在中序遍历的过程中，我们只是在发现逆序对时记录节点，这个操作的时间复杂度是 O(1)。
- 因此，总的时间复杂度是 O(n)。
2. 空间复杂度
- 空间复杂度主要取决于递归栈的深度，这通常与树的高度成正比。
- 在最坏的情况下，树完全不平衡，例如每个节点都只有左子节点或只有右子节点，递归栈的深度会是 O(n)。
- 在最好的情况下，树是完全平衡的，递归栈的深度是 O(log n)。
- 因此，空间复杂度介于 O(log n) 和 O(n) 之间，取决于树的形状。
五、总结知识点
二叉树的中序遍历：中序遍历是一种二叉树的遍历方式，按照“左-根-右”的顺序访问每个节点。对于二叉搜索树来说，中序遍历的结果是升序的。
递归：递归是一种编程技巧，用于解决可以分解为更小相似问题的问题。在这段代码中，
inorderTraversal函数通过递归的方式实现了二叉树的中序遍历。二叉搜索树（BST）的性质：二叉搜索树是一种特殊的二叉树，其中每个节点的值都满足左子树的所有节点值小于该节点的值，右子树的所有节点值大于该节点的值。
错误检测与纠正：代码通过比较中序遍历中相邻节点的值来检测BST中的错误，并记录下逆序对中的两个节点。最后，通过交换这两个节点的值来纠正错误。
指针（引用）的使用：在Java中，
prev、first和second是TreeNode类型的引用变量，用于在递归过程中跟踪节点。节点交换：代码中通过交换两个节点的值来恢复二叉搜索树的性质，而不需要交换节点的位置。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。