99. Recover Binary Search Tree

🟠   🔖  树 深度优先搜索 二叉搜索树 二叉树  🔗 LeetCode

题目

You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

Example 1:

Input: root = [1,3,null,null,2]

Output: [3,1,null,null,2]

Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.

Example 2:

Input: root = [3,1,4,null,null,2]

Output: [2,1,4,null,null,3]

Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.

Constraints:

• The number of nodes in the tree is in the range [2, 1000].
• -2^31 <= Node.val <= 2^31 - 1

Follow up: A solution using O(n) space is pretty straight-forward. Could you devise a constant O(1) space solution?

题目大意

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

解题思路

根据 BST 的性质，BST 的中序遍历是升序的，我们可以通过中序遍历来找到这两个错误节点，并交换它们的值，从而恢复 BST 的正确顺序。

1. 进行 BST 的中序遍历，并记录先前访问的节点 prev；
2. 在遍历过程中，如果发现当前节点的值小于先前节点的值，说明找到了一个错误节点；
3. 记录这两个错误节点，并继续遍历；
4. 遍历结束后，交换这两个错误节点的值，即完成修复操作；

代码

/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var recoverTree = function (root) {
  let prev = null;
  let first = null;
  let second = null;

  const traverse = (root) => {
    if (!root) return;
    traverse(root.left);
    if (prev != null && prev.val >= root.val) {
      if (first == null) {
        first = prev;
      }
      second = root;
    }
    prev = root;
    traverse(root.right);
  };
  traverse(root);
  const temp = first.val;
  first.val = second.val;
  second.val = temp;
};