convert-bst-to-greater-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: 500px; height: 341px;" />
<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>[0, 104]</code>.</li>
	<li><code>-104 &lt;= Node.val &lt;= 104</code></li>
	<li>All the values in the tree are unique.</li>
	<li><code>root</code> is guaranteed to be a valid binary search tree.</li>
</ul>

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

convertBST

Convert BST to Greater Tree

Tree

Depth-First Search

Binary Search Tree

Binary Tree

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 <code>node</code>&nbsp;的新值等于原树中大于或等于&nbsp;<code>node.val</code>&nbsp;的值之和。

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

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

注意：本题和 1038:&nbsp;<a href="https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/">https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/</a> 相同

&nbsp;

示例 1：

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

<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>

示例 3：

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

示例 4：

<pre>输入：root = [3,2,4,1]
输出：[7,9,4,10]
</pre>

&nbsp;

提示：

<ul>
	<li>树中的节点数介于 <code>0</code>&nbsp;和 <code>104</code>&nbsp;之间。</li>
	<li>每个节点的值介于 <code>-104</code>&nbsp;和&nbsp;<code>104</code>&nbsp;之间。</li>
	<li>树中的所有值 互不相同 。</li>
	<li>给定的树为二叉搜索树。</li>
</ul>