Version: Next
99.恢复二叉搜索树
难度 困难
给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？
You are given the root of a binary search tree (BST), where exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.
Follow up: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
示例 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]内 -231 <= Node.val <= 231 - 1
中序遍历法|空间复杂度O(n)
重要结论
对于二叉搜索树，其中序遍历结果是一个单调（递增、递减）序列
- 找中序遍历
逆序对，两个倒错的节点，可能引发 1 个 或 2 个逆序对
- 错误交换两个挨在一起、连续的元素（数值上紧挨）：会产生
1个逆序对- 错误交换两个没有挨在一起，彼此之间有距离（数值上，两数之间还有其他元素）：会产生
2个逆序对- 找到逆序对进行交换
- 只有1个逆序对：他们俩交换
- 2个逆序对：第一个逆序对的左 和 第二个逆序对的右 交换
- 合并两种情况：不论一个还是两个逆序对，都是找逆序对的
头和尾
正确 11 17 18 22 28 37 42 44 62 交换相邻的 22、28
产生一个逆序对11 17 18 282237 42 44 62 交换不相邻的 18、44
产生两个逆序对11 17 4422 28 37 42 1862
实现：
- 中序遍历二叉搜索树，每个节点都与上一个节点的值进行比较
- 如果找到逆序对，将逆序对的
头记录为错误节点1，尾记录为错误节点2
- 如果只出现一次逆序对：直接得到了正确头尾
- 如果出现两次逆序对：头就是第一次逆序对中的头，即错误节点1；尾要更新为第二个逆序对的尾
- 综上：只有错误节点1为 null 时才记录错误节点1，而错误节点2总是更新
- 时间复杂度：O(n)
- 空间复杂度：O(树高) = O(h) ，最坏情况下，树退化为链表，则空间复杂度为 O(n)，最好为 O(logn)