tree - 二叉树中的最大和 BST

Question

给定二叉树根，任务是返回任何子树的所有键的最大和，该子树也是二叉搜索树 (BST)。
假设 BST 定义如下：
- 节点的左子树仅包含键小于节点键的节点。
- 节点的右子树仅包含键大于节点键的节点。
- 左右子树也必须是二叉搜索树。

我试图通过在每个节点上检查它是否是 BST 然后找到它的总和来解决这个问题。
但我的方法是获得 TLE。解决这个问题的优化方法应该是什么？

标签： tree

Answer 1

您的方法的时间复杂度为 O(n^2)。

您可以在计算该子树中所有元素的总和时尝试检查子树是否为 BST。所以这将只需要遍历给定的树，将复杂度降低到 O(n)。

后序遍历应该可以工作。

如果您在实施这种方法时感到卡住，这可能会有所帮助：https ://www.youtube.com/watch?v=Zz7R9I9j2kI