added convert bst to greater tree solution

david-legend · david-legend · commit ae3eadda6830 · 2022-09-14T15:57:25.000Z
diff --git a/leetcode/src/binary_trees/lc_515_find_largest_value_in_each_tree_row/README.md b/leetcode/src/binary_trees/lc_515_find_largest_value_in_each_tree_row/README.md
@@ -0,0 +1,25 @@
+# [LC 515. Find Largest Value in Each Tree Row - Medium](https://leetcode.com/problems/convert-bst-to-greater-tree/description/)
+
+Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).
+
+### Example 1
+
+![Find Largest Value in Each Tree Row Example 1](https://assets.leetcode.com/uploads/2020/08/21/largest_e1.jpg)  
+
+```
+Input: root = [1,3,2,5,3,null,9]
+Output: [1,3,9]
+```
+
+### Example 2 
+
+```
+Input: root = [1,2,3]
+Output: [1,3]
+```
+
+
+### Constraints:
+
+- The number of nodes in the tree will be in the range [0, 104].
+- -2^31 <= Node.val <= 2^31 - 1
diff --git a/leetcode/src/binary_trees/lc_515_find_largest_value_in_each_tree_row/find_largest_value_in_each_tree_row.py b/leetcode/src/binary_trees/lc_515_find_largest_value_in_each_tree_row/find_largest_value_in_each_tree_row.py
@@ -0,0 +1,19 @@
+from collections import deque
+
+def largestValues(root):
+    if not root:
+        return []
+    
+    queue, result = deque([root]), []
+    while queue:
+        level_size, max_node_val = len(queue), float('-inf')
+        for _ in range(level_size):
+            curr_node = queue.popleft()
+            max_node_val = max(max_node_val, curr_node.val)
+            
+            if curr_node.left:
+                queue.append(curr_node.left)
+            if curr_node.right:
+                queue.append(curr_node.right)
+        result.append(max_node_val)
+    return result
diff --git a/leetcode/src/binary_trees/lc_530_minimum_absolute_diff_in_bst/README.md b/leetcode/src/binary_trees/lc_530_minimum_absolute_diff_in_bst/README.md
@@ -13,7 +13,7 @@ Output: 1
 
 ### Example 2
 
-![Minimum Absolute Difference in BST Example 1](https://assets.leetcode.com/uploads/2021/02/05/bst2.jpg)  
+![Minimum Absolute Difference in BST Example 2](https://assets.leetcode.com/uploads/2021/02/05/bst2.jpg)  
 
 ```
 Input: root = [1,0,48,null,null,12,49]
diff --git a/leetcode/src/binary_trees/lc_538_convert_bst_to_greater_tree/README.md b/leetcode/src/binary_trees/lc_538_convert_bst_to_greater_tree/README.md
@@ -0,0 +1,33 @@
+# [LC 538. Convert BST to Greater Tree - Medium](https://leetcode.com/problems/convert-bst-to-greater-tree/description/)
+
+Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of 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 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
+
+![Convert BST to Greater Tree Example 1](https://assets.leetcode.com/uploads/2019/05/02/tree.png)  
+
+```
+Input: root = [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]
+```
+
+### Example 2 
+
+```
+Input: root = [0,null,1]
+Output: [1,null,1]
+```
+
+
+### Constraints:
+
+- The number of nodes in the tree is in the range [0, 10^4].
+- -10^4 <= Node.val <= 10^4
+- All the values in the tree are unique.
+- root is guaranteed to be a valid binary search tree.
diff --git a/leetcode/src/binary_trees/lc_538_convert_bst_to_greater_tree/convert_bst_to_greater_tree.py b/leetcode/src/binary_trees/lc_538_convert_bst_to_greater_tree/convert_bst_to_greater_tree.py
@@ -0,0 +1,15 @@
+def convertBST(root):
+    def convertBstHelper(node):
+        nonlocal running_sum
+        if node is None: return
+        
+        convertBstHelper(node.right)
+        
+        node.val += running_sum
+        running_sum = node.val
+        
+        convertBstHelper(node.left)
+        
+    running_sum = 0
+    convertBstHelper(root)
+    return root
