maximum-sum-bst-in-binary-tree

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given a binary tree <code>root</code>, return the maximum sum of all keys of any sub-tree which is also a Binary Search Tree (BST).

Assume a BST is defined as follows:

<ul>
	<li>The left subtree of a node contains only nodes with keys less than the node&#39;s key.</li>
	<li>The right subtree of a node contains only nodes with keys greater than the node&#39;s key.</li>
	<li>Both the left and right subtrees must also be binary search trees.</li>
</ul>

&nbsp;
Example 1:

<img alt="" src="https://assets.leetcode.com/uploads/2020/01/30/sample_1_1709.png" style="width: 320px; height: 250px;" />

<pre>
Input: root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
Output: 20
Explanation: Maximum sum in a valid Binary search tree is obtained in root node with key equal to 3.
</pre>

Example 2:

<img alt="" src="https://assets.leetcode.com/uploads/2020/01/30/sample_2_1709.png" style="width: 134px; height: 180px;" />

<pre>
Input: root = [4,3,null,1,2]
Output: 2
Explanation: Maximum sum in a valid Binary search tree is obtained in a single root node with key equal to 2.
</pre>

Example 3:

<pre>
Input: root = [-4,-2,-5]
Output: 0
Explanation: All values are negatives. Return an empty BST.
</pre>

&nbsp;
Constraints:

<ul>
	<li>The number of nodes in the tree is in the range <code>[1, 4 * 104]</code>.</li>
	<li><code>-4 * 104 &lt;= Node.val &lt;= 4 * 104</code></li>
</ul>

maxSumBST

Maximum Sum BST in Binary Tree

Tree

Depth-First Search

Binary Search Tree

Dynamic Programming

Binary Tree

给你一棵以 <code>root</code> 为根的 二叉树 ，请你返回 任意 二叉搜索子树的最大键值和。

二叉搜索树的定义如下：

<ul>
	<li>任意节点的左子树中的键值都 小于 此节点的键值。</li>
	<li>任意节点的右子树中的键值都 大于 此节点的键值。</li>
	<li>任意节点的左子树和右子树都是二叉搜索树。</li>
</ul>

 

示例 1：

<img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/03/07/sample_1_1709.png" style="height: 250px; width: 320px;" />

<pre>
输入：root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
输出：20
解释：键值为 3 的子树是和最大的二叉搜索树。
</pre>

示例 2：

<img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/03/07/sample_2_1709.png" style="height: 180px; width: 134px;" />

<pre>
输入：root = [4,3,null,1,2]
输出：2
解释：键值为 2 的单节点子树是和最大的二叉搜索树。
</pre>

示例 3：

<pre>
输入：root = [-4,-2,-5]
输出：0
解释：所有节点键值都为负数，和最大的二叉搜索树为空。
</pre>

示例 4：

<pre>
输入：root = [2,1,3]
输出：6
</pre>

示例 5：

<pre>
输入：root = [5,4,8,3,null,6,3]
输出：7
</pre>

 

提示：

<ul>
	<li>每棵树有 <code>1</code> 到 <code>40000</code> 个节点。</li>
	<li>每个节点的键值在 <code>[-4 * 10^4 , 4 * 10^4]</code> 之间。</li>
</ul>