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 / 3BST 性质:中序遍历的结果为一个有序序列。因此我们将树看作有序数组。
两个例子:[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; } };