s*****n
发帖数: 956 | 1 开始问怎么计算这颗树有多少个节点。 这个就是简单递归。
后来问怎么把它存到一个sorted array.
void storeIntoSortedArray(Node* root, int* p)
{
//允许就在里面给 p allocate memory
}
怎么弄啊？有没有遍历一遍就能存好的方法？ |
P*******b
发帖数: 1001 | 2 bst不是本身就是in order的吗？
【在 s*****n 的大作中提到】
: 开始问怎么计算这颗树有多少个节点。 这个就是简单递归。
: 后来问怎么把它存到一个sorted array.
: void storeIntoSortedArray(Node* root, int* p)
: {
: //允许就在里面给 p allocate memory
: }
: 怎么弄啊？有没有遍历一遍就能存好的方法？
|
s*****n
发帖数: 956 | 3 可能我没表述清楚。bst的每个节点有一个左指针，一个右指针，一个数值。
要求把数值存到一个连续数组p。 不再以指针形式表示。
假设都是整数，那么可能需要先计算数的size，
然后 p = new int[ treeSize ];
【在 P*******b 的大作中提到】
: bst不是本身就是in order的吗？
|
s*****n
发帖数: 956 | 4 想了想，是不是要自己搞个stack来push pop? |
P*******b
发帖数: 1001 | 5 困难在哪里？
tree size一定要提前知道吗？
vector不行吗？
大数组不行吗？
【在 s*****n 的大作中提到】
: 可能我没表述清楚。bst的每个节点有一个左指针，一个右指针，一个数值。
: 要求把数值存到一个连续数组p。 不再以指针形式表示。
: 假设都是整数，那么可能需要先计算数的size，
: 然后 p = new int[ treeSize ];
|
s*****n
发帖数: 956 | 6 不知道size的话，没法allocate空间吧？有多少个数，就只需要多少memory存。
vector, 大数组应该都浪费空间了。 他的意思是就把数存在 p[] 里面
【在 P*******b 的大作中提到】
: 困难在哪里？
: tree size一定要提前知道吗？
: vector不行吗？
: 大数组不行吗？
|
P*******b
发帖数: 1001 | 7 realloc？不知道到底想考啥
【在 s*****n 的大作中提到】
: 不知道size的话，没法allocate空间吧？有多少个数，就只需要多少memory存。
: vector, 大数组应该都浪费空间了。 他的意思是就把数存在 p[] 里面
|
s*****n
发帖数: 956 | 8 struct Node {
Node* left;
Node* right;
int value;
};
这个是节点形式。
然后给我一个root节点， 然后让我遍历树，把value存到一个数组里面，要求结果还是
从小到大排列。
就是想考我怎么遍历这个树呀。 |
p******r
发帖数: 2999 | 9 in-order trav
【在 s*****n 的大作中提到】
: struct Node {
: Node* left;
: Node* right;
: int value;
: };
: 这个是节点形式。
: 然后给我一个root节点， 然后让我遍历树，把value存到一个数组里面，要求结果还是
: 从小到大排列。
: 就是想考我怎么遍历这个树呀。
|
s*****n
发帖数: 956 | 10 也就是还是得先遍历一次，知道大小。给p allocate memory， 然后再in-order遍历的
时候一个个存到p里面是吗？
我一直在想有没有方法一次就弄好罗。
【在 p******r 的大作中提到】
: in-order trav
|
p******r
发帖数: 2999 | 11 内存就是白菜，要么一次性申请超大内存，要么动态翻倍申请
你在面试里纠结这种没意义的问题没有任何意义
【在 s*****n 的大作中提到】
: 也就是还是得先遍历一次，知道大小。给p allocate memory， 然后再in-order遍历的
: 时候一个个存到p里面是吗？
: 我一直在想有没有方法一次就弄好罗。
|
