1373. Maximum Sum BST in Binary Tree¶
题目信息¶
- 题号:
1373
- 难度:
Hard
- 主题:
二叉树、二叉搜索树、后序遍历
- 原题:
- 重点:
在任意二叉树中选择一棵节点诱导子树,要求满足严格二叉搜索树性质,并最大化节点值总和;允许空子树和为零
题目重述¶
给定一棵二叉树。对于树中任意节点,以该节点为根并包含其全部后代的结构称为一棵子树。
请在所有满足严格二叉搜索树条件的子树中,返回节点值总和的最大值。若所有非空二叉搜索子树的和都为负,可选择空子树并返回 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
解释:虽然部分非空子树满足搜索树性质,但其和均为负,空子树更优。