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

题意思路：

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

方法一:中序遍历二叉树

先用中序遍历遍历二叉搜索树。

中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。若二叉树为空则结束返回，否则：

（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树
此时若得到的遍历结果有错误节点，则将结果按顺序标记，此时从左往右找那个大的数，并记录下答案，从右往左找小的那个数，并且索引值必大于前面记录下的索引，记录答案。

复杂度分析

时间复杂度：O(N)，N表示二叉树节点数量，递归中序遍历所有节点，遍历整个数组。

空间复杂度：O(N)，数组存储与读取数据

图文详解：

class Solution {
public:
    void function(vector<int>& result,int &pre,TreeNode* root){
        if(root == NULL)
            return;
        function(result,pre,root->left);   //左子树的中序遍历
        if(pre == -1)
            pre = root->val; //第一个节点，保存下
        if(root->val < pre){ //如果错误节点
            result.push_back(pre);  
            result.push_back(root->val);

        }
        pre = root->val;
        function(result, pre, root->right);  //右子树的中序遍历
    }
    vector<int> findError(TreeNode* root) {
        vector<int> result;
        int pre = -1;//标记节点
        function(result,pre, root);//中序遍历
        vector<int> res;
        if(result.size() < 2)//特判若小于两个错误节点的值
            return res;
        else{
            //将结果记录
            res.push_back(result[result.size()-1]);
            res.push_back(result[0]);

            return res;
        }
    }
};

方法二：递归枚举
递归搜索得到搜索二叉树的中序遍历结果

此时若得到的遍历结果有错误节点，则将结果按顺序标记，此时从左往右找那个大的数，并记录下答案，从右往左找小的那个数，并且索引值必大于前面记录下的索引，记录答案。

复杂度分析

时间复杂度：O(N)，N表示二叉树节点数量，递归中序遍历所有节点，遍历整个数组。

空间复杂度：O(N)，数组存储与读取数据

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

class Solution {
public:

    vector<int> v;
    vector<int> res;
    int flag=0;
    void function(TreeNode* root){
        if(root==NULL) return;//若根为空则返回
        function(root->left);//遍历左子树
        if(flag==2) return;//若左右子树遍历完返回
        if(!v.empty()&&root->val<v[v.size()-1]){
            if(flag==0){
                res.push_back(root->val);//记录中序遍历
                res.push_back(v[v.size()-1]);
                flag=1;
            }else{
                res[0]=root->val;
                flag=2;
            }
        }
        if(flag==2) return;
        v.push_back(root->val);
        function(root->right);//遍历右子树
    }
    vector<int> findError(TreeNode* root) {

        function(root);
        return res;
    }
};