binary-search-tree-to-greater-sum-tree

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

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>

第 135 场周赛

weekly-contest-135

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/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/problems/convert-bst-to-greater-tree/">https://leetcode.cn/problems/convert-bst-to-greater-tree/&nbsp; </a>相同