[LeetCode] 99. Recover Binary Search Tree
99题
一、问题描述
二、问题分析
本题很明显是之前98题的升级版。上一道题我们谈了如何确定一棵树是否为BST,而本题我们要找出两个出错的位置,并最终调整为BST。如何找出出错的位置呢?先看在上题的算法下什么情况会出错。显然,当本节点root的值大于中序节点遍历的上一个节点prev的值即出错。接下来再看出错的情况有哪些。1.出错的两个数相邻,比如12435。这种情况在遍历树的时候只会出错一次,即在4>3时出错,我们只需要将3,4交换。2.出错的两个数不相邻,比如14325。这种情况会出错两次,分别在4>3,3>2时出错,此时需交换的两个节点分别为第一次出错的前一个节点(4)与第二次出错的后一节点(2)。除此之外不会出现第三种情况。因此我们除了要像上个题一样,有一个prev指针记录中序遍历的前一个节点,还要额外增加p,q两个指针记录出错的两个节点。当第一次出错,p记录下prev节点,q记录下root节点(其中p节点一定是出错的节点,而q出错与否目前还不清楚)。如果只有一次出错,那么遍历完树只需交换pq即可。如果发生第二次出错,那么要更新q为第二次出错的root节点,之后再交换pq。这样做的时间复杂度为O(n),空间复杂度为O(1)。
三、问题求解
针对问题分析,以下是c++源代码:
/**
* 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) {
TreeNode *pre = NULL, *p = NULL, *q = NULL;
dfs(root, pre, p, q);
int temp = p->val;
p->val = q->val;
q->val = temp;
}
private:
void dfs(TreeNode* root, TreeNode* &pre, TreeNode* &p, TreeNode* &q) {
if (root == NULL) {
return ;
}
dfs(root->left, pre, p, q);
if (pre && pre->val > root->val) {
if (p == NULL) {
p = pre;
q = root;
}
else {
q = root;
}
}
pre = root;
dfs(root->right, pre, p, q);
}
};
需要注意的是,p,q节点在dfs参数中的调用必须以引用的形式(&p,&q),这样才能确保在dfs回到recoverTree时p与q的本体有被赋值。之后才能顺利交换。