# 1038.Binary-Search-Tree-to-Greater-Sum-Tree

## ้ข็ฎๅฐๅ

https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/

## ้ข็ฎๆ่ฟฐ

``````Given the root of a binary search tree with distinct values, modify it so that every node has a new value equal to the sum of the values of the original tree that are greater than or equal to node.val.

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

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

Example 1:
Input: [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]

Constraints:
The number of nodes in the tree is between 1 and 100.
Each node will have value between 0 and 100.
The given tree is a binary search tree.``````

## ไปฃ็ 

### Approach 1: Revered inorder Traversal

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
int pre = 0;
public TreeNode bstToGst(TreeNode root) {
if (root.right != null) bstToGst(root.right);
root.val = pre + root.val;
pre = root.val;
if (root.left != null) bstToGst(root.left);
return root;
}
}``````

### Approach #2 Iterative

Time & space: O(n).

``````class Solution {
public TreeNode bstToGst(TreeNode root) {
Deque<TreeNode> stk = new ArrayDeque<>();
TreeNode cur = root;
int sum = 0;
while (cur != null || !stk.isEmpty()) {
while (cur != null) {
stk.push(cur);
cur = cur.right;
}
cur = stk.pop();
sum += cur.val;
cur.val = sum;
cur = cur.left;
}

return root;
}
}``````

Last updated