###### tags: `LeetCode` `Recursion` `Tree` `Medium` `Inorder`
# LeetCode #99 [Recover Binary Search Tree](https://leetcode.com/problems/recover-binary-search-tree/)
### (Medium)

給你二叉搜索樹的根節點 root ，該樹中的兩個節點被錯誤地交換。請在不改變其結構的情況下，恢復這棵樹。


---
若對BST用中序遍歷, 則可以得到一個排序好的節點。

從整棵樹的最左邊節點(INT_MIN)開始尋找, 使用兩個指標紀錄兩個錯位的節點(這兩個節點一個過大一個過小), 最後將兩個節點的值交換即可。

---

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode *first=nullptr, *second=nullptr, *prev=new TreeNode(INT_MIN);
    void recoverTree(TreeNode* root) {
        helper(root);
        swap(first->val, second->val);
    }
    void helper(TreeNode* node){
        if(!node)return;
        helper(node->left);
        if(!first&&prev->val>node->val)first=prev;
        if(first&&prev->val>node->val)second=node;
        prev=node;
        helper(node->right);
    }
};