99.恢复二叉搜索树

恢复二叉搜索树

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

解析

中序遍历找到两个逆序节点并交换。

var recoverTree = function (root) {
  let first = null, second = null, prev = new TreeNode(-Infinity);
  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];
};