binary-search-tree-to-greater-sum-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 the <code>root</code> of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.

As a reminder, a binary search tree is a tree that satisfies these constraints:

<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/2019/05/02/tree.png" style="width: 400px; height: 273px;" />
<pre>
Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
</pre>

Example 2:

<pre>
Input: root = [0,null,1]
Output: [1,null,1]
</pre>

&nbsp;
Constraints:

<ul>
	<li>The number of nodes in the tree is in the range <code>[1, 100]</code>.</li>
	<li><code>0 &lt;= Node.val &lt;= 100</code></li>
	<li>All the values in the tree are unique.</li>
</ul>

&nbsp;
Note: This question is the same as 538: <a href="https://leetcode.com/problems/convert-bst-to-greater-tree/" target="_blank">https://leetcode.com/problems/convert-bst-to-greater-tree/</a>

bstToGst

Binary Search Tree to Greater Sum Tree

Tree

Depth-First Search

Binary Search Tree

Binary Tree

给定一个二叉搜索树&nbsp;<code>root</code>&nbsp;(BST)，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。

提醒一下， 二叉搜索树 满足下列约束条件：

<ul>
	<li>节点的左子树仅包含键 小于 节点键的节点。</li>
	<li>节点的右子树仅包含键 大于 节点键的节点。</li>
	<li>左右子树也必须是二叉搜索树。</li>
</ul>

&nbsp;

示例 1：

<img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/05/03/tree.png" style="height:273px; width:400px" />

<pre>
输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
</pre>

示例 2：

<pre>
输入：root = [0,null,1]
输出：[1,null,1]
</pre>

&nbsp;

提示：

<ul>
	<li>树中的节点数在&nbsp;<code>[1, 100]</code>&nbsp;范围内。</li>
	<li><code>0 &lt;= Node.val &lt;= 100</code></li>
	<li>树中的所有值均 不重复&nbsp;。</li>
</ul>

&nbsp;

注意：该题目与 538:&nbsp;<a href="https://leetcode-cn.com/problems/convert-bst-to-greater-tree/">https://leetcode-cn.com/problems/convert-bst-to-greater-tree/&nbsp; </a>相同