99. Recover Binary Search Tree

Leetcode link

解题思路

本题随意调换了 BST 的两个元素。

我们知道，当对 BST 进行先序遍历的时候，得到的是一个递增序列，在递增序列任意交换两个数有两种可能：

1. 两个交换的数是相邻的
2. 两个交换的数不相邻

那么我们可以用一个指针 prev 记录上一个中序遍历的节点，然后跟当前节点对比，如果 prev 比较大，则把 prev 跟当前节点一起存放到一个数组 target 中。

这样子一次遍历之后，有两种可能：

1. target 中有一个元素（因为两个交换的数比邻），那么只需要交换元素中两个指针的 val 就好。
2. target 中有两个元素（因为两个交换的数不相邻），那么只需要交换 第一个元素的第一个指针的 val 与 第二个元素的第二个指针的 val 就好。

C++

class Solution {
 public:
  vector<pair<TreeNode*, TreeNode*>> target;
  TreeNode* prev = nullptr;
  void dfs(TreeNode* node) {
    if (node == nullptr) {
      return;
    }
    dfs(node->left);
    if (prev && (prev->val > node->val)) {
      target.push_back({prev, node});
    }
    prev = node;
    dfs(node->right);
  }
  void recoverTree(TreeNode* root) {
    dfs(root);
    if (target.size() == 1) {
      // 相邻情况
      swap(target[0].first->val, target[0].second->val);
    } else if (target.size() == 2) {
      // 不相邻情况
      swap(target[0].first->val, target[1].second->val);
    }
  }
};

Javascript

var recoverTree = function(root) {
    let target = [];
    let prev = null;

    const dfs = (node)=>{
        if(!node){
            return;
        }

        dfs(node.left);
        if(prev && prev.val > node.val) {
            target.push([prev, node]);
        }
        prev = node;
        dfs(node.right);
    }

    dfs(root);
    if(target.length === 1) {
      // 相邻情况
        [target[0][0].val, target[0][1].val] = [target[0][1].val, target[0][0].val];
    } else if(target.length === 2) {
      // 不相邻情况
        [target[0][0].val, target[1][1].val] = [target[1][1].val, target[0][0].val];
    }
};