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

1038. Binary Search Tree to Greater Sum Tree

题目地址

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

538: https://leetcode.com/problems/convert-bst-to-greater-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;
  }
}