a****o
发帖数: 45 | 1 从geeksforgeeks看得
Two elements of BST are swapped by mistake. You have to restore the tree
without changing its structure. |
v***n
发帖数: 5085 | 2 in order travel so to build a sorted array and find the two elements first? |
v***d
发帖数: 51 | 3 有个想法：
按照inorder遍历这个bst，存到一个数组。在数组中找到这两个数（e.g.二分查找直到
发现局部最大和最小），然后swap它们在bst上的位置。 |
v***d
发帖数: 51 | 4 和你的方法重了，呵呵。
【在 v***n 的大作中提到】
: in order travel so to build a sorted array and find the two elements first?
|
a*******y
发帖数: 1040 | 5 inorder is not necessary, just use recursion to make sure min<=p->data < max
, update min and max depending on left or right, save the two nodes and swap
the data. |
a****o
发帖数: 45 | 6 For example,
2
/ \
3 4
/
1
Actually, we need to swap 2 and 3. However, 2 is valid because initial min=
INT_min and max= INT_MAX. How to deal this case?
max
swap
【在 a*******y 的大作中提到】
: inorder is not necessary, just use recursion to make sure min<=p->data < max
: , update min and max depending on left or right, save the two nodes and swap
: the data.
|
p*****2
发帖数: 21240 | 7
=
左树错误，右树正确，它自己一定是错误的。
【在 a****o 的大作中提到】
: For example,
: 2
: / \
: 3 4
: /
: 1
: Actually, we need to swap 2 and 3. However, 2 is valid because initial min=
: INT_min and max= INT_MAX. How to deal this case?
:
: max
|
p*****2
发帖数: 21240 | 8
max
swap
我基本也是这个思路。
【在 a*******y 的大作中提到】
: inorder is not necessary, just use recursion to make sure min<=p->data < max
: , update min and max depending on left or right, save the two nodes and swap
: the data.
|
p*****2
发帖数: 21240 | |
i**********e
发帖数: 1145 | 10 这题最坏情况要O（n）吧，必须检查每一个节点。
基本思路就是 inorder traversal 和保存前一个节点，但不用额外的空间。
TreeNode *first, *second, *prev;
void recoverHelper(TreeNode *p) {
if (!p) return;
recoverHelper(p->left);
if (prev && prev->val > p->val) {
if (!first)
first = prev;
second = p;
}
prev = p;
recoverHelper(p->right);
}
void recover(TreeNode *root) {
first = second = prev = NULL;
recoverHelper(root);
swap(first->val, second->val);
} |
|
|
p*****2
发帖数: 21240 | 11
赞。确实是这个规律。
【在 i**********e 的大作中提到】
: 这题最坏情况要O（n）吧，必须检查每一个节点。
: 基本思路就是 inorder traversal 和保存前一个节点，但不用额外的空间。
: TreeNode *first, *second, *prev;
: void recoverHelper(TreeNode *p) {
: if (!p) return;
: recoverHelper(p->left);
: if (prev && prev->val > p->val) {
: if (!first)
: first = prev;
: second = p;
|
i**********e
发帖数: 1145 | 12 刚加了这道题 “Recover Binary Search Tree".
递归的解法可行吗？我感觉好像不太行得通。 |
p*****2
发帖数: 21240 | 13
你这个不就是递归吗？
我当时没想到用global variable, 搞了半天没搞对。用global variable 看起来就好
多了。
【在 i**********e 的大作中提到】
: 刚加了这道题 “Recover Binary Search Tree".
: 递归的解法可行吗？我感觉好像不太行得通。
|
p*****2
发帖数: 21240 | 14
你这个不就是递归吗？
我当时没想到用global variable, 搞了半天没搞对。用global variable 看起来就好
多了。
【在 i**********e 的大作中提到】
: 刚加了这道题 “Recover Binary Search Tree".
: 递归的解法可行吗？我感觉好像不太行得通。
|
i**********e
发帖数: 1145 | 15 我意思是你们之前讨论那个递归的思路 － 传 min,max 到下面。
【在 p*****2 的大作中提到】
:
: 你这个不就是递归吗？
: 我当时没想到用global variable, 搞了半天没搞对。用global variable 看起来就好
: 多了。
|
p*****2
发帖数: 21240 | 16
那个好像不行。我就按照那个思路没搞定。后来在那个思路上修修补补总是不通。我觉
得你的才是正确的思路。规律很清晰，很好理解。
【在 i**********e 的大作中提到】
: 我意思是你们之前讨论那个递归的思路 － 传 min,max 到下面。
|
N********n
发帖数: 8363 | 17
如果只有两个的话应该好办。假设是升序，错位的两个数的特征是一个比
它身后的数大，另一个比它身前的书小。那么你就写一个的遍历程序找到
这两个节点然后交换一下就可以了。O(N)复杂度。
【在 a****o 的大作中提到】
: For example,
: 2
: / \
: 3 4
: /
: 1
: Actually, we need to swap 2 and 3. However, 2 is valid because initial min=
: INT_min and max= INT_MAX. How to deal this case?
:
: max
|
