algorithm - 给定一棵二叉树，找到最大的子树，即二叉搜索树

Question

我在一次采访中被问到这个问题。我以寻找所有子树并检查其中是否有 bst 的天真方法开始我的回答。在这个过程中，我们会记录目前看到的最大bst的大小。

还有比这更好的方法吗？

Answer 1

如果你这样做会怎样:

1. 反转图表的权重
2. 以这种方式使用 Kruskal 算法。

---

一个。从您的边集中选择权重最低的边。

仅当添加该边不会破坏您的 bst 约束时才创建树。

从您的边集中删除该边。

您最终可能会得到几棵树(因为当不满足 bst 约束时丢弃边可能会使您断开原始图)，因此只需选择具有更多节点的树。