调整搜索二叉树中两个错误的节点

一、题目

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

Leetcode 99 题：https://leetcode.cn/problems/recover-binary-search-tree/

二、分析

一个二叉树搜索树，他的中序遍历一定是升序的。如果像题目中的一样，有两个节点的值被错误的交换，那么对应的中序遍历的结果中就会有一个或者两个地方出现 arr[i] > arr[i+1]。因此我们有三步操作。

• 通过中序遍历，拿到数组
• 遍历数组，拿到一个或者两个地方的错误节点
• 最后遍历二叉树搜索树，替换到对应的错误节点即可

#include <vector>
#include <algorithm>

struct Node {
    int val;
    Node* left;
    Node* right;

    explicit Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    void adjust_node(Node* head) {
        in_order(head);
        set_err_pos();
        reserve(head, 2);
    }

private:
    void in_order(Node* head) {
        if (head == nullptr) {
            return;
        }
        in_order(head->left);
        vec_.emplace_back(head->val);
        in_order(head->right);
    }

    void set_err_pos() {
        int head1 = -1;
        int head2 = -1;
        for (int i = 0; i < vec_.size()-1; i++) {
            if (vec_[i] > vec_[i+1]) {
                head2 = i+1;
                if (head1 == -1) {
                    head1 = i;
                } else {
                    break;
                }
            }
        }
        err_pos_.first = vec_[head1];
        err_pos_.second = vec_[head2];
    }

    void reserve(Node* head, int count) {
        if (head == nullptr) {
            return;
        }
        if (head->val == err_pos_.first || head->val == err_pos_.second) {
            head->val = head->val == err_pos_.first ? err_pos_.second : err_pos_.first;
            count--;
        }
        if (count == 0) {
            return;
        }
        reserve(head->left, count);
        reserve(head->right, count);
    }

private:
    std::vector<int> vec_;
    std::pair<int, int> err_pos_;
};

时间复杂度：O(n) 空间复杂度：O(n)