aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--bst_greater_sum_tree.c33
-rw-r--r--bst_greater_sum_tree.py35
2 files changed, 68 insertions, 0 deletions
diff --git a/bst_greater_sum_tree.c b/bst_greater_sum_tree.c
new file mode 100644
index 0000000..713c582
--- /dev/null
+++ b/bst_greater_sum_tree.c
@@ -0,0 +1,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); }
diff --git a/bst_greater_sum_tree.py b/bst_greater_sum_tree.py
new file mode 100644
index 0000000..0f5bd87
--- /dev/null
+++ b/bst_greater_sum_tree.py
@@ -0,0 +1,35 @@
+# 1038. Binary Search Tree to Greater Sum Tree
+
+"""
+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.
+"""
+
+
+# Definition for a binary tree node.
+class TreeNode(object):
+ def __init__(self, accum=0, left=None, right=None):
+ self.val = val
+ self.left = left
+ self.right = right
+
+
+class Solution(object):
+ accum = 0
+
+ def bstToGst(self, root):
+ """
+ :type root: TreeNode
+ :rtype: TreeNode
+ """
+ if root.right:
+ self.bstToGst(root.right)
+ root.accum = self.accum = self.accum + root.val
+ if root.left:
+ self.bstToGst(root.left)
+ return root