a*******8
发帖数: 2299 | 1 给出一颗tree, 该tree没有任何特征, 即可以有多个子节点, 父节点和左右子节点也没
有大小关系。但每个节点的值不相等。 现给出几个值, 如(12, 24) 请找出从根节点到
值为12 和24的节点的subtree | p********7
发帖数: 549 | | t****a
发帖数: 1212 | 3 some python like code here:
def get_subtree(tree, values):
newtree = copy(tree)
filter_tree(newtree, values)
def filter_tree(tree, values):
if len(values)==0:
return NULL
elif tree.value in values:
values.remove(tree.value)
tree.left = filter_tree(tree.left, values)
tree.right = filter_tree(tree.right, values)
return tree | d*********i
发帖数: 628 | 4 先排序一遍生成2叉树
然后找到12，再找到24 《--用递归前序遍历
排序建立树时间是O(n)吧，不太确定
前序遍历worst case是要找的值在叶子上，
那O=depth of the tree:
worst case是每个点只有一个child,那depth = N
其他情况，depth = Log2(N) |
|
