二叉树中的最大二叉搜索树和

Question

给定二叉树根节点，任务是返回所有子树中键值和最大且也是二叉搜索树（BST）的子树。
假设BST的定义如下:
- 节点的左子树仅包含键值小于该节点键值的节点。
- 节点的右子树仅包含键值大于该节点键值的节点。
- 左、右子树均为二叉搜索树。

我尝试通过检查每个节点是否为BST，然后计算其和来解决此问题。但是我的方法超时了。应该采用什么优化方法来解决此问题？

- Vishesh Aggarwal

Answer 1

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

可以在计算该子树中所有元素的和时检查子树是否为BST。这样只需要对给定的树进行一次遍历，将复杂度降至 O(n)。

应该使用后序遍历。

如果在实现此方法时感到困惑，这可能会有所帮助：https://www.youtube.com/watch?v=Zz7R9I9j2kI

- alGOds