[leetcode] 99. Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

解题思路:
首先理解一下题目的意思，给定一棵BST，其中有两个元素交换了位置，要求恢复这课BST

解题思路仍然是中序遍历，我发现遇到BST的时候，大部分情况下都可以考虑一下中序遍历，由于BST中序遍历的输出是一个有序的数组，因此可以通过比较上一次节点和当前节点找到两个交换的节点，最后交换两个节点的值即可。
代码如下：

class Solution {
public:
    void inorderTravel(TreeNode* root, TreeNode* & first, TreeNode* & second, TreeNode* & prev)
    {
        if(root == NULL) return;
        inorderTravel(root->left,first,second,prev);
        if(first == NULL && prev != NULL && prev->val > root->val)//注意要保证prev不为空，否则prev->val会越界
            first = prev;
        if(first != NULL && prev != NULL && prev->val > root->val)
            second = root;
            
        prev = root;
        inorderTravel(root->right,first,second,prev);
        return;
    }
    void recoverTree(TreeNode* root) {
        TreeNode* first = NULL, *second = NULL, *prev = NULL;
        inorderTravel(root,first,second,prev);
        swap(first->val,second->val);
        return;
    }
};

参考资料：https://discuss.leetcode.com/topic/3988/no-fancy-algorithm-just-simple-and-powerful-in-order-traversal