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

找到搜索二叉树中的两个错误结点

一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请按升序输出这两个错误节点的值。(每个节点的值各不相同)

输入：{1,2,3}
返回值：[1,2]

方法一 中序遍历

首先先了解一下搜索二叉树的性质:

• 如果该树的左子树不为空,则左子树的所有点的权值小于根结点
• 如果该树的右子树不为空,则右子树的所有点的权值大于根结点
• 所以点点左右子树都为搜索二叉树
  

根据上述的性质能得出对该树进行中序遍历得出的结果一定是一个有序序列
中序遍历:

所以这题通过中序遍历得出的序列中，正序遍历第一次大小关系错误的值就是要找的第一个点,然后逆序找第一次大小关系错的值就是我们要找的第二个点。

int dfn[100000], tot = 0;

    vector<int> findError(TreeNode* root) {
        // write code her
        getdfs(root);
        vector<int> ans;
        for(int i = 1;i < tot ;i ++){    //正序找第一个错误的值
            if(dfn[i] > dfn[i + 1]){
                ans.push_back(dfn[i]); break;
            }
        }
        for(int i = tot ; i >= 1; i --){    //逆序找第一个错误的值
            if(dfn[i] < dfn[i - 1]){
                ans.push_back(dfn[i]); break;
            }
        }
        if(ans[0] > ans[1]) swap(ans[0], ans[1]);    //如果第一个大于第二个则交换
        return ans;
    }
    void getdfs(TreeNode* root){//中序遍历
        if(!root){
            return;
        }
        getdfs(root->left);
        dfn[++ tot] = root->val;
        getdfs(root->right);
    }

时间复杂度: O(n) 遍历一棵树
空间复杂度: O(n) 存储一棵树的结点值

方法二 中序遍历在遍历中求结果

定义一个pre,用来存储上一个访问的节点,如果第一次找到当前点比上一个点值要小那就是交换点的第一个点，然后继续判断找到最后一个上一个点比当前点要大的点那那个点就是交换点的第二个点,与方法一的想法一致只是在遍历中去判断相邻两个数的关系。

vector<int> ans;
    int cnt = 1;
    TreeNode * pre;
    vector<int> findError(TreeNode* root) {
        // write code her
        pre = NULL;
        ans.push_back(0);    //在vector中开辟长度为2的空间
        ans.push_back(0);
        getdfs(root);
        return ans;
    }
    void getdfs(TreeNode* root){
        if(!root){
            return;
        }
        getdfs(root->left);
        if(pre == NULL) pre = root;
        int p = root->val;
        //找交换的第一个点
        if(cnt == 1 && pre->val > root->val){    //找到第一个当前点比上一个点小的点
            ans[cnt] = pre->val; cnt --;
        }
        //找交换的第二个点
        if(cnt == 0 && pre->val > root->val){    //找到最后一个上一个点比当前点大的点
            ans[cnt] = root->val;
        }
        pre = root;
        getdfs(root->right);
    }

时间复杂度: O(n) 遍历一遍树
空间复杂度: O(1) 只使用了若干个变量