algorithm - 在百万二叉搜索树的列表中查找下面的树是否存在

Question

例如，

考虑以下树，检查它们是否存在于 BST 列表中。

           5
          / \
         4   6
        / \
       1   3


       3
      / \
     2   4

如何解决这个问题？

Answer 1

根据根对列表进行排序（如果根相同，则左节点等）。对每个查询树进行二分搜索。

如果查询数量与列表中的元素数量相当，则此方法有效。复杂性：( (n+m)logn) 其中 m 是查询数，n 是列表中的元素数。

如果查询的数量很少，蛮力搜索是有效的。

Answer 2

这个问题的答案是将列表中的所有树放入哈希表中，以便对树进行恒定时间搜索。

Answer 3

我会把它作为答案提出来，以便人们可以根据需要做出变化。

一种天真的方法是只扫描列表，比较每个节点，一旦发现要比较的两棵树有差异，就继续查看列表中的下一个。=> O(N) 其中 N 是节点的总数。