99.js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var recoverTree = function (root) {
  let prev = root.val,
    first,
    second

  function inorder(node) {
    if (!node) return

    inorder(node.left)

    if (prev.val > node.val) {
      if (!first) {
        first = prev
      }
      second = node
    }
    prev = node

    inorder(node.right)
  }

  inorder(root)
  ;[first.val, second.val] = [second.val, first.val]
}

var recoverTree = function (root) {
  let first = null,
    second = null,
    prev = null

  let current = root

  while (current !== null) {
    if (current.left == null) {
      if (prev !== null && prev.val > current.val) {
        if (first == null) {
          first = prev
        }
        second = current
      }
      prev = current
      current = current.right
    } else {
      let predecessor = current.left
      while (predecessor.right !== null && predecessor.right !== current) {
        predecessor = predecessor.right
      }

      if (predecessor.right === null) {
        predecessor.right = current
        current = current.left
      } else {
        predecessor.right = null

        if (prev !== null && prev.val > current.val) {
          if (first === null) {
            first = prev
          }
          second = current
        }

        prev = current
        current = current.right
      }
    }
  }

  const temp = first.val
  first.val = second.val
  second.val = temp
}