diff options
-rw-r--r-- | bst_greater_sum_tree.c | 33 | ||||
-rw-r--r-- | bst_greater_sum_tree.py | 35 |
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 |