99-恢复二叉搜索树

LeetCode 99. 恢复二叉搜索树

给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。

示例 1：

输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

method

中序遍历，每次前向节点大于当前节点，就把pre和root插入数组中，这样最后数组中的第一个和最后一个节点就是互换的

第一次找到的pre肯定是最终结果的，但root不一定是与之交换的那个，所以还要继续看看后面有没有，有的话就更新root，同时也可以退出了

vector<TreeNode*> res;
TreeNode *pre = nullptr;
void dfs(TreeNode *root) {
    if (!root) return;
    dfs(root->left);
    if (pre && pre->val > root->val) {
        res.push_back(pre);
        res.push_back(root);
    }
    pre = root;
    dfs(root->right);
}
void recoverTree(TreeNode* root) {
    dfs(root);
    swap(res[0]->val, res.back()->val);	// 3 2 2 1
}

迭代版

void recoverTree(TreeNode* root) {
    TreeNode *x = nullptr;
    TreeNode *y = nullptr;
    TreeNode *pre = nullptr;
    stack<TreeNode*> st;
    while (!st.empty() || root) {
        while (root) {
            st.push(root);
            root = root->left;
        }
        root = st.top();
        st.pop();
        if (pre && pre->val > root->val) {
            y = root;
            if (x == nullptr) {
                x = pre;
            } else break;	// 说明pre已经确定，现在y又确定，可以退出了
        }
        pre = root;
        root = root->right;
    }
    swap(x->val, y->val);
}