二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。
示例 1:
输入: [1,3,null,null,2]
1
/
3
\
2
输出:
[3,1,null,null,2]
3
/
1
\
2
示例 2:
输入: [3,1,4,null,null,2]
3
/ \
1 4
/
2
输出: [2,1,4,null,null,3]
2
/ \
1 4
/
3
进阶:
使用 O(n) 空间复杂度的解法很容易实现。
你能想出一个只使用常数空间的解决方案吗？
思路：
不考虑常数空间复杂度则使用中序遍历就好，如果要用常数空间复杂度则需要使用二叉线索树，树的右指针指向下一个节点，首先从根节点往前构建线索，然后在顺着线索往后遍历进行判断，具体看代码。
代码：
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
TreeNode first,second;
public void recoverTree(TreeNode root) {
TreeNode cur = root, pre = null;
while (cur != null){
// 如果该子树根节点没有左子树，则不需要构建线索
if (cur.left == null){
detect(pre, cur);
pre = cur;
cur = cur.right;
}
else {
// 左指针节点比根节点小，构建线索要往前，所以当根节点线索完成后需要创建左指针节点的线索
TreeNode node = cur.left;
// 找到左指针节点的最右节点，这是根节点的前一个节点
while (node.right != null && node.right != cur) node = node.right;
// 创建线索
if (node.right == null){
node.right = cur;
cur = cur.left;
}
// 如果线索已经存在，需要进行二叉搜索树判断，并把线索去掉
else {
detect(pre, cur);
pre = cur;
cur = cur.right;
// 去掉线索
node.right = null;
}
}
}
//交换错误的两个节点的值
if (first != null && second != null) {
first.val = first.val + second.val;
second.val = first.val - second.val;
first.val -= second.val;
}
}
// 监测是否符合二叉搜索树
private void detect(TreeNode pre, TreeNode cur){
if (pre != null && pre.val > cur.val){
if (first == null) first = pre;
second = cur;
}
}
}
