s******n
发帖数: 20 | 1 这是Leetcode上的一篇文章：
leetcode.com/2010/09/saving-binary-search-tree-to-file.html
里面的重建BST代码我觉得有问题：
void readBSTHelper(int min, int max, int &insertVal,
BinaryTree *&p, ifstream &fin) {
if (insertVal > min && insertVal < max) {
int val = insertVal;
p = new BinaryTree(val);
if (fin >> insertVal) {
readBSTHelper(min, val, insertVal, p->left, fin);
readBSTHelper(val, max, insertVal, p->right, fin);
}
}
}
void readBST(BinaryTree *&root, ifstream &fin) {
int val;
fin >> val;
readBSTHelper(INT_MIN, INT_MAX, val, root, fin);
}
比如
10
/
5
/ \
4 8
的pre-order是： 10 5 4 8.
显然读到8上面的算法就不工作了，大家有没有什么方法可以重建BST in O(n)
我能想到的最好方法就是starting search from the root node and insert了。 | r*********n
发帖数: 4553 | 2 为什么不对呢？
这里面比较tricky的地方是 readBSTHelper里面的 insertVal是int&，在build 4的时
候，fin>>insertVal就把insertVal的值从4变成了8。 | s******n
发帖数: 20 | 3 原来如此。
谢谢提醒。
【在 r*********n 的大作中提到】
: 为什么不对呢？
: 这里面比较tricky的地方是 readBSTHelper里面的 insertVal是int&，在build 4的时
: 候，fin>>insertVal就把insertVal的值从4变成了8。
|
|
