Lstmxx的空间

99. 恢复二叉搜索树

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

链接

function recoverTree(root: TreeNode | null): void {
  let n1 = null
  let n2 = null
  let pre = null
  traverse(root)
  function traverse(root: TreeNode | null) {
    if (root === null) return
    traverse(root.left)
    if (pre && root.val < pre.val) {
      n2 = root
      if (!n1) n1 = pre
      else return
    }
    pre = root
    traverse(root.right)
  }
  if (n1 && n2) {
    const temp = n1.val
    n1.val = n2.val
    n2.val = temp
  }
}

O(1)复杂度

const swap = (x, y) => {
    const temp = x.val
    x.val = y.val
    y.val = temp
}

var recoverTree = function(root) {
    let x = null, y = null, pred = null, predecessor = null

    while (root !== null) {
      if (root.left !== null) {
        // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
        predecessor = root.left
        while (predecessor.right !== null && predecessor.right !== root)
          predecessor = predecessor.right

        // 让 predecessor 的右指针指向 root，继续遍历左子树
        if (predecessor.right === null) {
          predecessor.right = root
          root = root.left
        }
        // 说明左子树已经访问完了，我们需要断开链接
        else {
          if (pred !== null && root.val < pred.val) {
            y = root
            if (x === null) {
                x = pred
            }
          }
          pred = root

          predecessor.right = null
          root = root.right
        }
      }
      // 如果没有左孩子，则直接访问右孩子
      else {
        if (pred !== null && root.val < pred.val) {
            y = root
            if (x === null) {
                x = pred
            }
        }
        pred = root

        root = root.right
      }
    }
    swap(x, y)
}