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

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

http://www.nowcoder.com/practice/4582efa5ffe949cc80c136eeb78795d6

题目的主要信息：

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

方法一：中序非递归

具体做法：

使用栈辅助进行二叉树的中序遍历：栈记录当前节点，不断往左深入，直到左边子树为空，再弹出栈顶（即为当前子树的父节点），然后再访问其右子树，其中每棵子树都遵循左中右的次序。

而搜索二叉树的中序遍历恰好是升序的，我们可以用一个数组记录中序遍历的结果。然后遍历该数组，查看前一个元素比后一个元素大的情况。交换位置的有可能有两种情况，如下图所示：

情况一：相邻位置交换，直接将大小相反的两个元素加入答案；
情况二：不相邻位置交换，需要先按情况一操作，在已经找到相邻大小相反的元素的情况下再次遇到，则弹出答案中末尾元素，然后加入新遇到错误。

alt

class Solution {
public:
    vector<int> findError(TreeNode* root) {
        vector<int> nums;
        vector<int> res;
        if(root == NULL)
            return res;
        TreeNode* p = NULL;
        stack<TreeNode*> s;   //用栈辅助建立中序
        while (!s.empty() || root != NULL) {
            while (root != NULL) {
                s.push(root);
                root = root->left;   //中序遍历每棵子树从最左开始
            }
            p = s.top(); //弹出要遍历的节点
            s.pop();
            nums.push_back(p->val); //加入数组
            root = p->right; //进入右子节点
        }
        bool flag = false;
        for(int i = 0; i < nums.size() - 1; i++){ //中序遍历的数字必须递增序，如果不是则是错误节点的值
            //错误位置有可能相邻，有可能不相邻，分两种情况
            if(nums[i] > nums[i + 1]){ 
                if(!flag){ //先记录第一次遇到的两个错误
                    res.push_back(nums[i]);
                    res.push_back(nums[i + 1]);
                    flag = true;
                }else{ //第二次出现错误，记录另一个
                    res.pop_back();
                    res.push_back(nums[i + 1]);
                }
            }
        }
        sort(res.begin(), res.end()); //升序
        return res;
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，中序遍历二叉树全部节点一次，之后遍历数组又相当于遍历二叉树一次
空间复杂度： $O (n)$ ，记录节点值的数组及辅助栈的空间

方法二：中序递归

具体做法：

我们也可以利用递归对二叉树进行中序遍历，同时用一个指针表示递归的当前节点的前序节点，每次比较当前节点与前序节点的大小关系，整个类似方法一的数组比较了，记录下前序节点与当前节点值逆序的情况，也分两种，因此找到第一个相反后继续中序遍历查看还有没有第二次逆序，如果有更新第二个记录指针。

最后将两个指针的取出，做排序即可。

class Solution {
public:
    TreeNode* pre = NULL; //记录前序节点
    TreeNode* first = NULL; 
    TreeNode* second = NULL;
    void inOrder(TreeNode* root){ //中序递归遍历
        if(root == NULL)
            return;
        inOrder(root->left); //先进入左节点
        if(pre == NULL) //记录前序节点
            pre = root;
        if(root->val < pre->val){ //找到中序遍历当前节点小于上一个节点（错误节点）
            if(first == NULL){ //记录第一个数
                first = pre;
                second = root;
            }else //记录第二个数
                second = root;
        }
        pre = root; //当前节点
        inOrder(root->right); //右子节点
    }
    
    vector<int> findError(TreeNode* root) {
        inOrder(root); //递归找到两个错误的节点
        vector<int> res;
        if(first != NULL && second != NULL) //找到两个点
            res = {first->val, second->val}; 
        sort(res.begin(), res.end()); //排序
        return res;
    }
};

复杂度分析：