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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

#include <climits>
class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root
     * @return int整型vector
     */
    TreeNode* t1 = nullptr;                     //记录第一个错误点
    TreeNode* t2 = nullptr;                     //记录第二个错误点
    TreeNode* temp = nullptr;                   //记录中序遍历中，当前结点的上一个结点
    int max = INT_MIN;
    bool flag = false;                          //用于区别第一次找到错误点和第二次找到错误点
    void findT(TreeNode* root){
        if(root->left != nullptr){
            findT(root->left);
        }
        if(max > root->val && flag == false){   //如果第一次找到错误点，则先假设交换的两个点是相邻点
            t1 = temp;
            t2 = root;
            flag = true;
        }else if(max > root->val){              //如果不是交换的两个点不是相邻点则会进入该条件
            t2 = root;
        }
        temp = root;                            //在进入下一轮递归前，将当前结点记录下来
        max = root->val;
        if(root->right != nullptr){
            findT(root->right);
        } 
    }
    vector<int> findError(TreeNode* root) {
        // write code here
        vector<int> answer;
        findT(root);
        answer.push_back(t2->val);
        answer.push_back(t1->val);
        return answer;

    }
};

看c++的题解中好像空间复杂度都是O(n)，小伙子就献丑一下(●'◡'●)

空间复杂度为O(n)的题解中的思路都是，用中序遍历和vector来将搜索二叉树记录下来，

然后找到一个错误点(相邻结点交换) 如：（1，2，3，5，4，6，7）

或者两个错误点(非相邻结点交换)。 如：（1，2，6，4，5，3，7）

如果是一个错误点（4），则将错误处（4）和错误处的前一个结点（5）作为答案返回

如果是两个错误结点（4，3），则将第一个错误结点的前一个结点（6）和第二个错误结点（3）作为答案返回

空间复杂度为O(1)的思路是，用一个结点指针temp记录中序遍历中当前结点的上一个结点

当第一次遇到错误结点时，将错误结点和错误结点的前一个结点记录下来

如果接下来的遍历不在碰到错误结点时，则直接返回前面记录下来的两个结点

如果接下来再次碰到错误结点，则将当前错误结点和第一次碰到的错误结点的前一个结点作为答案