题解 | 找到搜索二叉树中两个错误的节点

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类 the root
     * @return int整型vector
     */
    TreeNode* prev;      // 上一个中序节点
    TreeNode* first;     // 第一次逆序时的前一个
    TreeNode* second;    // 最后一次逆序时的当前
    vector<int> findError(TreeNode* root) {
        // write code here
        first = second = prev= nullptr;
        inorder(root);
        int a = first->val, b = second->val;
        if (a > b) swap(a, b);
        return {a, b};
    }
    void inorder(TreeNode* node) {
        if (!node) return;
        inorder(node->left);
        if (prev && prev->val > node->val) {
            if (!first) first = prev;        // 第一次发现逆序
            second = node;                   // 每次逆序都更新 second
        }
        prev = node;
        inorder(node->right);
    }
};