Leetcode BST树找错

题目描述

二叉搜索树（BST）中的两个节点被错误地交换了，

请在不改变树的结构的情况下恢复这棵树。

备注；

用O(n)的空间解决这个问题的方法太暴力了，你能设计一个常数级空间复杂度的算法么？

 

思路：由于二叉搜索树中序遍历总是递增序列   那么采用中序遍历方式

如图所示，包含两种交换 

1. 第一相邻的交换  那么其中序遍历结果包含一组相邻逆序对
2. 另外一种是不相邻的交换，那么其中序遍历结果包含两组相邻逆序对

求解思路是寻找到相邻逆序对的第一个元素first  和最后一个元素second  最后交换即可

那么在第一次遇见逆序对时 first被赋值之后保存不变，而second随时被更新

TreeNode* first=NULL;
      TreeNode* second=NULL;
      TreeNode* pre=NULL;//上一个节点
    void recoverTree(TreeNode *root) {
      
        inorder(root);
        if(first && second)
            swap(first->val,second->val);
        
        
    }
    void inorder(TreeNode* root) //中序遍历  是从小到大的顺序   那么找到不符合部分即可
    {
        if(root==NULL)
            return;
   
        inorder(root->left);//先遍历左子树
        if(pre && pre->val>root->val)  //比较左孩子yu
        {
            if(first==NULL) //第一个节点还没有被赋值
                first=pre;
            second=root;
        }
        //由于pre仅仅在此处被赋值  而每一个不为空的root都被按照顺序访问到  那么pre总是指向root的前一个
        pre=root; //上一个节点赋值为root节点  进入右子树        
        inorder(root->right);
        
    }