b******d
发帖数: 17 | 1 回馈版面。就不说公司名了。好像这题以前还没有在本版出现过（？）
由一个输入数组可以构建一个BST。现已知一个BST，问有多少种数组可以构建出这个树。
比如[3,1,2,4]和[3,1,4,2]会建出同一个树（数组有先后顺序）
搜了一下，这个解答和面试官告诉我的是一样的：
http://www.ieee.org.cn/dispbbs.asp?BoardID=67&ID=64169&replyID= |
b*******y
发帖数: 2048 | 2 没有看懂题目。。。一个数组不是可能生成许多种树么？ |
C***U
发帖数: 2406 | 3 他是bst树
所以给定来的顺序以后树bst就确定了
可以用递归算法来做这个问题吧
N(k)=2(N(x)+N(y))
这里x是left subtree的node数
y是right subtree的node数
x+y=k-1
这里的2倍是因为left subtree和right subtree的进来顺序可以整体交换一下
不知道这个样对不对
【在 b*******y 的大作中提到】
: 没有看懂题目。。。一个数组不是可能生成许多种树么？
|
n**s
发帖数: 2230 | 4 应该不只这个数。
首先应该是左边个数乘以右边个数。左右两边数组次序不变，还可以交叉。这样要再乘
以交叉的数目。
可以定义为
N(k)=N(x)*N(y)*(number of x and y arrays interleaved)
【在 C***U 的大作中提到】
: 他是bst树
: 所以给定来的顺序以后树bst就确定了
: 可以用递归算法来做这个问题吧
: N(k)=2(N(x)+N(y))
: 这里x是left subtree的node数
: y是right subtree的node数
: x+y=k-1
: 这里的2倍是因为left subtree和right subtree的进来顺序可以整体交换一下
: 不知道这个样对不对
|
C***U
发帖数: 2406 | 5 恩 对 应该是乘 不是加
然后那个interleaved的数字是x+y里面取x的组合数
【在 n**s 的大作中提到】
: 应该不只这个数。
: 首先应该是左边个数乘以右边个数。左右两边数组次序不变，还可以交叉。这样要再乘
: 以交叉的数目。
: 可以定义为
: N(k)=N(x)*N(y)*(number of x and y arrays interleaved)
|
b******d
发帖数: 17 | 6 对，是这么算。最后他问我复杂度。。没有说好。。。
【在 C***U 的大作中提到】
: 恩 对 应该是乘 不是加
: 然后那个interleaved的数字是x+y里面取x的组合数
|
j********e
发帖数: 1192 | 7 复杂度就是O(n)吧
【在 b******d 的大作中提到】
: 对，是这么算。最后他问我复杂度。。没有说好。。。
|
b******d
发帖数: 17 | 8 要计算子树的节点数呀
【在 j********e 的大作中提到】
: 复杂度就是O(n)吧
|
a*******y
发帖数: 1040 | |
b******d
发帖数: 17 | 10 就是给定一个bst，求有多少种顺序可以生成这样的树
【在 a*******y 的大作中提到】
: 给定来的顺序是什么意思？ 数组的顺序是什么顺序
|
