algorithm - 给定一棵二叉树，计算其中存在的二叉搜索树的数量

Question

给定一棵二叉树，我们要计算其中的二叉搜索树的数量。每个叶节点都是一个BST
我使用了以下方法。
对于 bt 中的每个节点，检查它是否是 bst
上述方法的时间复杂度为 O(n²)。我们如何才能以 O(n) 的有效方式做到这一点。

Answer 1

如果我对问题的理解正确，可以按如下方式解决；一个目标是计算作为二叉搜索树根的节点数。如前所述，每个叶子都是二叉搜索树的根。非叶节点 a 是二分搜索的根当且仅当 a 的左 child 是二叉搜索树，b 的右 child 是二叉搜索树的根，a 左 child 下所有值的最大值不大于 a 的值和上面的最小值a 右 child 下的所有值都大于或等于 a 的值。可以通过递归评估来评估此属性，递归评估恰好访问每个节点一次，这会导致线性运行时间限制。