给定 n 个元素 1,2,.........,n 上的二叉搜索树的后序遍历 P。您必须确定以 P 作为其后序遍历的唯一二叉搜索树。执行此操作的最有效算法的时间复杂度是多少？
(a) theeta(logn)
(b) theeta(n)
(c) theeta(nlogn)
(d) none of the above, as tree cannot be uniquely determined
答案是(b)，请说明解决方法。如果我们已经获得后序遍历，我们是否需要应用 sorting(O(nlogn)) 来按顺序计算？
最佳答案
不，您不必对它进行排序。
在后序遍历中你可以找到一些隐藏的信息。喜欢:
- 最后一个元素总是树根
- 前面所有大于根的元素都是右子树的一部分。所有较小的元素都是左子树的一部分。
- 您可以递归地应用上述规则。
之所以如此，是因为您只有不同的元素。如果有重复，遍历的树就不可能是唯一的。
这是一个示例实现(在 Python 中)显示了这一点:
from collections import deque
def visit(in_queue, limit = None):
if len(in_queue) == 0 or in_queue[-1] < limit:
return None
root = in_queue.pop()
right = visit(in_queue, max(root, limit))
left = visit(in_queue, limit)
if left is None and right is None:
return root
else:
return (left, root, right)
def print_graphviz(tree):
if not isinstance(tree, tuple):
return tree
left = print_graphviz(tree[0])
right = print_graphviz(tree[2])
if left is not None: print tree[1], '->', left
if right is not None: print tree[1], '->', right
return tree[1]
def make_tree(post_order):
return visit(deque(post_order))
print 'digraph {'
print print_graphviz(make_tree([0, 2, 1, 4, 3, 6, 8, 7, 5]))
print '}'
像这样运行:
python test.py | dot -Tpng | display
你会得到一个漂亮的树输出:
关于algorithm - 门 2008 : Time Complexity of Binary Search Tree，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31956224/