LeetCode Daily Question 27

May 10th 2022

5 月 10 日 每日一题

题目：99. 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.

1
2
3
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.

思路

本题核心是利用 inorder traversal 检测错误点（BSF 的 inorder 应该为从小到大），如果检测到两组顺序不同的 node，则为第一组 node 的第一个位置和第二组 node 的第二个位置。因此需要两个 pointer first 和 second 记录这两个位置。需要注意的是 prev 的初始值应该为 infinitMin。
注意 prev 初始为 infmin

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    TreeNode *firstRemove, *secondRemove, *prev;
    void recoverTree(TreeNode* root) {
        prev = new TreeNode(INT_MIN);
        inorderHelper(root);
        swap(firstRemove->val, secondRemove->val);
    }
    void inorderHelper(TreeNode *root){
        if(!root)
            return;
        inorderHelper(root->left);
        if(firstRemove == nullptr && root->val < prev->val)
            firstRemove = prev;
        if(firstRemove != nullptr && root->val < prev->val)
            secondRemove = root;
        prev = root;
        inorderHelper(root->right);
    }
};

,
  1. 5 月 10 日 每日一题
    1. 题目：99. Recover Binary Search Tree
    2. 思路
    3. 代码