1373. Maximum Sum BST in Binary Tree

题目信息

题号:

1373

难度:

Hard

主题:

二叉树、二叉搜索树、后序遍历

原题:

LeetCode 1373

重点:

在任意二叉树中选择一棵节点诱导子树,要求满足严格二叉搜索树性质,并最大化节点值总和;允许空子树和为零

题目重述

给定一棵二叉树。对于树中任意节点,以该节点为根并包含其全部后代的结构称为一棵子树。

请在所有满足严格二叉搜索树条件的子树中,返回节点值总和的最大值。若所有非空二叉搜索子树的和都为负,可选择空子树并返回 0。

树中节点数不超过 4 * 10^4,节点值位于 [-4 * 10^4,4 * 10^4]。

自建示例

整棵树本身是二叉搜索树:

输入:root = [4,2,6,1,3,5,7]
输出:28
解释:整棵树满足搜索树性质,所有节点值之和为 28。

所有节点值为负时返回零:

输入:root = [-2,-3,-1]
输出:0
解释:虽然部分非空子树满足搜索树性质,但其和均为负,空子树更优。