d99. Recover Binary Search Tree

題目 連結

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.

翻譯

給定一個二元搜尋樹 (BST) 的 root ，其中樹的兩個節點的值被錯誤地交換了。恢復樹而不改變其結構。

測試資料

Example 1: 範例 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: 範例 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.

解題思路

這題也算簡單，需要知道 BST 中序是由小到大。只要找到兩數值排序怪怪的就就把他們作交換

程式碼

/**
 * 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.
 */
// [3,1,4,null,null,2]
//       3
//      / \
//     1   4
//        /
//       2
//
let prev = null;
let node1 = null;
let node2 = null;
// 1 2 3
// 3 2 1

var recoverTree = function (root) {
  prev = null;
  node1 = null;
  node2 = null;
  solve(root);

  [node1.val, node2.val] = [node2.val, node1.val];
  return root;
};

let solve = (node) => {
  if (node == null) return null;
  solve(node.left);

  if (prev != null && prev.val > node.val) {
    if (!node1) node1 = prev;
    node2 = node;
  }
  prev = node;

  solve(node.right);
};