algorithm - 门 2008 : Time Complexity of Binary Search Tree

Question

给定 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)) 来按顺序计算？

Answer 1

不，您不必对它进行排序。

在后序遍历中你可以找到一些隐藏的信息。喜欢:

• 最后一个元素总是树根
• 前面所有大于根的元素都是右子树的一部分。所有较小的元素都是左子树的一部分。
• 您可以递归地应用上述规则。

之所以如此，是因为您只有不同的元素。如果有重复，遍历的树就不可能是唯一的。

这是一个示例实现(在 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

你会得到一个漂亮的树输出: