r*****e
发帖数: 146 | 1 二叉查找树中两个节点被错误的交换了，如何有效找出他们。有没有比较neat的解法？
谢谢 | l***i
发帖数: 1309 | 2 assume all nodes are distinct
1. recursively find maxL and minR, which are max element in root->left
subtree and min element in root->right subtree
2. if maxL > minR, then these two are swapped elements
3. if maxL > root value, then maxL is swapped with root
4. if root value > minR, then minR is swapped with root
5. the only case remain is maxL < root < minR, in this case recurse on both
root->left and root->right because the two swapped nodes must be in the same
subtree now. | h****n
发帖数: 1093 | 3 inorder travese即可找第一个不对路和最后一个不对路的交换即可
二叉查找树中两个节点被错误的交换了，如何有效找出他们。有没有比较neat的解法？
谢谢
★ Sent from iPhone App: iReader Mitbbs Lite 7.56
【在 r*****e 的大作中提到】
: 二叉查找树中两个节点被错误的交换了，如何有效找出他们。有没有比较neat的解法？
: 谢谢
| l*********8
发帖数: 4642 | 4 怎么找maxL 和 minR？ 遍历一遍？
both
same
【在 l***i 的大作中提到】
: assume all nodes are distinct
: 1. recursively find maxL and minR, which are max element in root->left
: subtree and min element in root->right subtree
: 2. if maxL > minR, then these two are swapped elements
: 3. if maxL > root value, then maxL is swapped with root
: 4. if root value > minR, then minR is swapped with root
: 5. the only case remain is maxL < root < minR, in this case recurse on both
: root->left and root->right because the two swapped nodes must be in the same
: subtree now.
|
|
