99. Recover Binary Search Tree

https://leetcode.com/problems/recover-binary-search-tree/

BST中序遍历为从小到大排序。因此做中序遍历找到一到两处不符合从小到大的地方，第一处的第一个和第二处的第二个即被swap过的元素（如果只有一处，那它俩本身就是）。

/*
 * @lc app=leetcode id=99 lang=cpp
 *
 * [99] Recover Binary Search Tree
 *
 * https://leetcode.com/problems/recover-binary-search-tree/description/
 *
 * algorithms
 * Hard (35.51%)
 * Likes:    931
 * Dislikes: 51
 * Total Accepted:    127.3K
 * Total Submissions: 357.6K
 * Testcase Example:  '[1,3,null,null,2]'
 *
 * Two elements of a binary search tree (BST) are swapped by mistake.
 * 
 * Recover the tree without changing its structure.
 * 
 * Example 1:
 * 
 * 
 * Input: [1,3,null,null,2]
 * 
 * 1
 * /
 * 3
 * \
 * 2
 * 
 * Output: [3,1,null,null,2]
 * 
 * 3
 * /
 * 1
 * \
 * 2
 * 
 * 
 * Example 2:
 * 
 * 
 * Input: [3,1,4,null,null,2]
 * 
 * ⁠ 3
 * ⁠/ \
 * 1   4
 * /
 * 2
 * 
 * Output: [2,1,4,null,null,3]
 * 
 * ⁠ 2
 * ⁠/ \
 * 1   4
 * /
 * ⁠ 3
 * 
 * 
 * Follow up:
 * 
 * 
 * A solution using O(n) space is pretty straight forward.
 * Could you devise a constant space solution?
 * 
 * 
 */
/**
 * 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 recoverTree(TreeNode* root) {
        if (root == nullptr) return;
        stack<TreeNode*> s;
        TreeNode *pre = nullptr;
        const auto push_left = [&](TreeNode *cur) {
            while (cur != nullptr) {
                s.push(cur);
                cur = cur->left;
            }
        };
        push_left(root);
        TreeNode *last = nullptr, *x = nullptr, *y = nullptr;
        while (!s.empty()) {
            const auto cur = s.top();
            if (last != nullptr && last->val > cur->val) {
                if (x == nullptr) x = last;
                y = cur;
            }
            last = cur;
            s.pop();
            if (cur->right != nullptr) push_left(cur->right);
        }
        const auto tmp = x->val;
        x->val = y->val;
        y->val = tmp; 
    }
};