我在一次采访中被问到这个问题。我以寻找所有子树并检查其中是否有 bst 的天真方法开始我的回答。在这个过程中，我们会记录目前看到的最大bst的大小。
还有比这更好的方法吗？
最佳答案
如果你这样做会怎样:
- 反转图表的权重
- 以这种方式使用 Kruskal 算法。
一个。从您的边集中选择权重最低的边。
仅当添加该边不会破坏您的 bst 约束时才创建树。
从您的边集中删除该边。
您最终可能会得到几棵树(因为当不满足 bst 约束时丢弃边可能会使您断开原始图)，因此只需选择具有更多节点的树。
关于algorithm - 给定一棵二叉树，找到最大的子树，即二叉搜索树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12188157/