leetcode0099. 恢复二叉搜索树- medium

1 题目：99. 恢复二叉搜索树

官方标定难度：

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

示例 1：

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

示例 2：

输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

提示：

树上节点的数目在范围 [2, 1000] 内
$-2^{31}<=Node.val<=2^{31}-1$

进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？

2 solution

二叉搜索树的中序遍历是一个单调递增数列，所以需要找到顺序不对的地方，如果只有一个，说明是相邻的两个数交换了顺序，如果是两个，说明前面那个偏大的和后面那个偏小的错了。

代码

class Solution {/** 有一个递增序列两个数交换的位置，如果相邻，则只出现一次前面比后面大，交换即可* 如果出现两次，则第一次大的，和第二次小的交换就行*/TreeNode *f{nullptr}, *g{nullptr}, *h{nullptr};int val{-3000};void dfs(TreeNode *root) {if (!root) return;dfs(root->left);if (root->val < val) {if (!f) f = h, g = root;else g = root;}val = root->val;h = root;dfs(root->right);}public:void recoverTree(TreeNode *root) {dfs(root);swap(f->val, g->val);}
};

结果