leetcode-99-Recover-Binary-Search-Tree

描述


Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

分析


二叉排序树中,两个节点被交换了,要求写一个算法,将该树恢复成二叉排序树。如果用中序遍历,得到一个序列,可以很快找到交换的两个节点,调整之后再生成树,但题目要求空间复杂度是O(1).

实际上可以用pre指向中序遍历过程中的前一个节点,如果找到了次序错误的节点,那么pre指向的就是第一个次序错误的节点,如果二叉排序树中交换的节点不是相邻的,那么之后的遍历过程中肯定还能找到次序错误的节点,这时就可以找到第二个次序错误的节点了。

解决方案1(C++)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
* 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 *res1, *res2;
TreeNode* pre;
void recoverTree(TreeNode* root) {
if(!root) {
return;
}
res1 = res2 = pre = NULL;
in_order(root);
swap(res1->val, res2->val);
}
void in_order(TreeNode* root) {
if(!root) {
return;
}
if(root->left) {
in_order(root->left);
}
if(pre && root->val < pre->val) {
if(res1 == NULL) {
res1 = pre;
res2 = root;
}else {
res2 = root;
}
}
pre = root;
if(root->right) {
in_order(root->right);
}
}
};

题目来源