leetcode 99. 恢复二叉搜索树

原题传送门

思路

既然是二叉搜索树，那肯定中序遍历了。当然还有Morris遍历算法（我还没学~）
中序遍历的话，对于二叉搜素树来说就是从小到大进行排序。那么在遍历的过程中我们可以记录出现逆序的情况。

情况一 (需要交换的节点不相邻)

第一个逆序对的前一个节点为需要交换的节点。first指针记录
第二个逆序对的后一个节点为需要交换的节点。second指针记录
情况二（需要交换的节点相邻）
特殊情况，只有一个逆序对，两个直接交换。如果在边界也是一样的。
第一个逆序对，两个节点都需要记录。
第一个逆序的第二节点指针，我命名为t_second。
由于在中序遍历的过程中，我们不能知道具体能遇见几个逆序对。所以记录第一个逆序对的时候两个节点都需要记录。

show your code

class Solution {
public:
    void recoverTree(TreeNode* root) {
         if (!root) return;
        // 第一个逆序对的 前一个。
        // 第二个逆序对的 后一个。
        // 特殊情况，只有一个逆序对，两个直接交换。

        TreeNode * first = NULL;
        TreeNode * second = NULL;
        TreeNode * t_second = NULL;
        TreeNode * tmp = root;

        stack<TreeNode *> st;

        while (tmp) {
            st.push(tmp);
            tmp = tmp->left;
        }
        // 取中序遍历过程中，第一个被遍历的节点（最小的点）。作为前一个节点。
        TreeNode * pre = st.top();      
        st.pop();
        tmp = pre->right;

        while (st.size() || tmp){       //接着刚才的继续中序遍历。
            while (tmp) {
                st.push(tmp);
                tmp = tmp->left;
            }
            TreeNode * t = st.top();
            st.pop();
            if (pre->val > t->val){
                if (!first){        // 第一个逆序对。遇见的第一个逆序对。
                    first = pre;
                    t_second = t;   // 如果只有一个逆序对会用上这个值。
                } else if (!second){
                    second = t;     // 遇见第二个逆序对。
                }
            }
            pre = t;
            tmp = t->right;
        }
        if (!second) second = t_second; //如果没有记录到第二个值。
        int t = first->val;             //可以使用swap函数进行交换。
        first->val = second->val;
        second->val = t;
    }
};