[99] 恢复二叉搜索树

给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。

进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？

示例 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

var recoverTree = function(root) {
  let prev = null;
  let first = null;
  let second = null;
  if(!root) return null;
  helper(root, null)
  
  const temp = first.val;
  first.val = second.val;
  second.val = temp;
  return root;

  function helper(node) {
    if(!node) return;
    helper(node.left);
    if(!prev) {
      prev = node;
    } else {
      if(node.val < prev.val) {
        if(!first) first = prev;
        second = node;
      }
      prev = node;
    }
    helper(node.right);
  }
};

这也是一道二叉树查找的变体题。我们需要三个指针，prev指向当前节点的上一个节点，first与second分别记录两个需要交换的节点。接下来我们只需要遍历这棵树查找即可，我们这里选择了中序遍历。

在遍历时，我们需要比较prev与当前节点的值大小，若prev更大，说明搜索树错乱，此时需要交换节点值。如果first此时不存在，将first指向prev，否则说明之前已出现更需要替换的节点，则first维持原有指向。second指向当前节点。

遍历结束后，交换first和second的值即可。