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?
解題思路
利用二叉搜尋樹中序周遊的結果是一個有序遞增序列的性質,在中序周遊的過程中尋找需要交換資料的兩個結點。在這過程中有兩種情況需要考慮:需要交換的元素在中序下相鄰,如
[1, 2, 4, 3, 5]
;需要交換的元素在中序下不相鄰,如
[1, 5, 3, 4, 2
。
代碼如下:
/**
* 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 {
private:
void inOrderFindErrorNode(TreeNode *root, TreeNode*& e1,
TreeNode*& e2, TreeNode*& pre) {
if (root == NULL) return;
inOrderFindErrorNode(root->left, e1, e2, pre);
if (pre != NULL && pre->val >= root->val) {
e2 = root;
if (e1 == NULL) {
e1 = pre;
}
}
pre = root;
inOrderFindErrorNode(root->right, e1, e2, pre);
}
public:
void recoverTree(TreeNode* root) {
TreeNode *pre = NULL, *e1 = NULL, *e2 = NULL;
inOrderFindErrorNode(root, e1, e2, pre);
swap(e1->val, e2->val);
}
};