题目地址

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

题目描述：恢复二叉搜索树

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下，恢复这棵树。

示例：

例 1:

输入: [1,3,null,null,2]

1 / 3 \ 2

输出: [3,1,null,null,2]

3 / 1 \ 2

例 2:

输入: [3,1,4,null,null,2]

3 / \ 1 4 / 2

输出: [2,1,4,null,null,3]

2 / \ 1 4 / 3

解答

BST 性质：中序遍历的结果为一个有序序列。因此我们将树看作有序数组。

两个例子：[1,3,2,4]、[4,2,3,1]

在中序遍历中，只需要利用一个 pre 节点和当前节点比较，如果 pre 节点的值大于当前节点的值，那么就是我们要找的逆序的数字。分别用两个指针 first 和 second 保存即可。如果找到第二组逆序的数字，我们就把 second 更新为当前节点。最后把 first 和 second 两个的数字交换即可。

代码：

/** * 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: TreeNode* first, * second, *pre; int flag = 0; void order( TreeNode* root){ if( !root) return ; order( root->left); if( flag == 0) pre = root, flag++; if( pre->val > root->val){ if( flag == 1 ) //第一次寻找 前一个元素大于后一个元素 flag++, first = pre, second = root, pre = root; else if( flag == 2 ) //第二次，若寻找到，则更新 flag++, second = root; } else pre = root; order( root->right); } void recoverTree(TreeNode* root) { order( root); //交换 first 和 second 的结点 int temp = first->val; first->val = second->val, second->val = temp; } };