leetcode

Leetcode Solutions (0x6A73)
git clone https://git.pngu.org/leetcode
Log | Files | Refs | Submodules | README

bst_greater_sum_tree.c (995B)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 1038. Binary Search Tree to Greater Sum Tree
#include "leetcode.h"

/*
 * given the 'root' of a binary search tree, convert it to a greater tree such
 * that every key o 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 the following 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 also be binary search trees.
 */

struct TreeNode {
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
};

struct TreeNode *dfs(struct TreeNode *root) {
  int accum = 0;
  if (!root)
    return NULL;
  else {
    dfs(root->right);
    accum += root->val;
    root->val = accum;
    dfs(root->left);
    return root;
  }
}

struct TreeNode *bstToGst(struct TreeNode *root) { return dfs(root); }