来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/recover-binary-search-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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

解答

  1. 把二叉树转为排序数组
  2. 从排序数组中找到那两个排序不对的节点

  3. 两个节点值替换

    1. /**
    2. * Definition for a binary tree node.
    3. * function TreeNode(val, left, right) {
    4. *     this.val = (val===undefined ? 0 : val)
    5. *     this.left = (left===undefined ? null : left)
    6. *     this.right = (right===undefined ? null : right)
    7. * }
    8. */
    9. /**
    10. * @param {TreeNode} root
    11. * @return {void} Do not return anything, modify root in-place instead.
    12. */
    13. var recoverTree = function(root) {
    14.  let nodes = [];
    15.  function transitionToSortedArray (node, low, high) {
    16.      if (!node) return null;
    18.      transitionToSortedArray(node.left, low, node.val);
    19.      nodes.push(node);
    20.      transitionToSortedArray(node.right, node.val, high);
    21.  }
    22.  transitionToSortedArray(root, -Infinity, Infinity);
    24.  const sortedNodes = Array.from(nodes).sort((prevNode, node) => prevNode.val - node.val);
    25.  let toRecoverNodes = [];
    27.  nodes.forEach((node, i) => {
    28.      if (node !== sortedNodes[i]) {
    29.          toRecoverNodes.push(node);
    30.      }
    31.  })
    33.  if (toRecoverNodes.length === 2) {
    34.      let temp = toRecoverNodes[0].val;
    35.      toRecoverNodes[0].val = toRecoverNodes[1].val;
    36.      toRecoverNodes[1].val = temp;
    37.  }
    38. };

    优化

    优化需要解决一个问题：
    如何从数组中找到两个不符合要求的节点？

  4. 第一个节点出现的条件：当前值比下一个值大，为 null 取当前值

  5. 第二个节点出现的条件：当前值比下一个值大，取下一个值 ``` const inorder = (root, nums) => { if (root === null) {
    1.  return;
    } inorder(root.left, nums); nums.push(root.val); inorder(root.right, nums); }

const findTwoSwapped = (nums) => { const n = nums.length; let index1 = -1, index2 = -1; for (let i = 0; i < n - 1; ++i) { if (nums[i + 1] < nums[i]) { index2 = i + 1; if (index1 === -1) { index1 = i; } else { break; } } } let x = nums[index1], y = nums[index2]; return [x, y]; }

const recover = (r, count, x, y) => { if (r !== null) { if (r.val === x || r.val === y) { r.val = r.val === x ? y : x; if (—count === 0) { return; } } recover(r.left, count, x, y); recover(r.right, count, x, y); } }

var recoverTree = function(root) { const nums = []; inorder(root, nums); const [first, second] = findTwoSwapped(nums); recover(root, 2, first, second); }; ```