1373. Maximum Sum BST in Binary Tree ==================================== 题目信息 -------- :题号: 1373 :难度: Hard :主题: 二叉树、二叉搜索树、后序遍历 :原题: `LeetCode 1373 `_ :重点: 在任意二叉树中选择一棵节点诱导子树,要求满足严格二叉搜索树性质,并最大化节点值总和;允许空子树和为零 题目重述 -------- 给定一棵二叉树。对于树中任意节点,以该节点为根并包含其全部后代的结构称为一棵子树。 请在所有满足严格二叉搜索树条件的子树中,返回节点值总和的最大值。若所有非空二叉搜索子树的和都为负,可选择空子树并返回 ``0``。 树中节点数不超过 ``4 * 10^4``,节点值位于 ``[-4 * 10^4,4 * 10^4]``。 自建示例 -------- 整棵树本身是二叉搜索树: .. code-block:: text 输入:root = [4,2,6,1,3,5,7] 输出:28 解释:整棵树满足搜索树性质,所有节点值之和为 28。 所有节点值为负时返回零: .. code-block:: text 输入:root = [-2,-3,-1] 输出:0 解释:虽然部分非空子树满足搜索树性质,但其和均为负,空子树更优。