# 99-Recover Binary Search Tree
###### tags: `Medium`
* Question:
https://leetcode.com/problems/recover-binary-search-tree/
* Key:
1. 如何用對struct為TreeNode進行遍尋比較?
先輸入root再對左子樹進行遞迴，並且用a, b紀錄要交換的兩節點，遞迴過程中，如果有發現錯誤，就進行記錄到a, b，否則就一直更新root為前一個節點，接著對右子樹進行遞回，這樣才能確保檢查順序為:左>根?->移動節點->根>右?
3. 遍尋後，若發現錯誤，如何做交換?
記錄節點a, b後指向value即可交換
4. 思考:如果題目不止一個錯誤怎麼辦? 遍尋到哪就先做修正(交換)，修正後，再繼續遍尋，可以嗎?
5. DFS

* Reference:
1. https://ithelp.ithome.com.tw/articles/10279073?sc=rss.iron
2. https://hwchang0417.wordpress.com/2018/11/07/leetcode-99-recover-binary-search-tree/
* Hint:
1. 要先知道BST的定義:
a. 若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值；
b. 若任意節點的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值；
c. 任意節點的左、右子樹也分別為二元搜尋樹；

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    
    void recover(TreeNode* r, TreeNode* &prev, TreeNode* &a, TreeNode* &b){
        if(r){
            recover(r->left, prev, a, b);
            
            if(r->val < prev->val){
                if(!a) a = prev;
                b = r;
            }
            prev = r;
            
            recover(r->right, prev, a, b);
        }
    }
    
    void recoverTree(TreeNode* root) {
        TreeNode p(INT_MIN);
        TreeNode *a = NULL, *b = NULL, *prev = &p;
        recover(root, prev, a, b);
        
        if(a && b){
            int tmp = a->val;
            a->val = b->val;
            b->val = tmp;
        }
    }
};