第五周 Leetcode 99. Recover Binary Search Tree （HARD）

Leetcode99 给定一个 二叉搜索树，其中两个节点被交换，写一个程序恢复这颗BST.

只想到了时间复杂度O（n）空间复杂度O（h） h为树高的解法，还没想到空间O(1）的解法。

交换的情况只有两种，

case1 两个节点在树中（中序遍历序列）相邻，

case2 两个节点在树中（中序遍历序列）不相邻。

只要三个指针 Pre first second 即可记录两种case

class Solution {  
public:  
    TreeNode *first;  
    TreeNode *second;  
    TreeNode *pre;  
       
    void inOrder(TreeNode *root){  
        if (root==NULL)  
            return;  
        inOrder(root->left);  
        if (pre == NULL){pre = root;}  
        else {  
            if (pre->val > root->val){  
                if (first==NULL) {first = pre;}  
                second = root;  
            }  
            pre = root;  
        }  
        inOrder(root->right);  
    }  
    void recoverTree(TreeNode *root) {  
        // Start typing your C/C++ solution below  
        // DO NOT write int main() function  
        pre = NULL;  
        first = NULL;  
        second= NULL;  
        inOrder(root);  
        int val;  
        val = first->val;  
        first->val=second->val;  
        second->val=val;  
        return;  
    }  
};