Comment on page

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

1038. 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;
}
}