8000 add 1038 · noodlesfate1/Leetcode-1@e28b4a3 · GitHub
[go: up one dir, main page]
Skip to content

Commit e28b4a3

Browse files
fishercoder1534fishercoder1534
committed
add 1038
1 parent ba4b6b1 commit e28b4a3

File tree

3 files changed

+86
-0
lines changed

3 files changed

+86
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -29,6 +29,7 @@ Your ideas/fixes/algorithms are more than welcome!
2929
|-----|----------------|---------------|---------------|---------------|--------|-------------|-------------
3030
|1051|[Height Checker](https://leetcode.com/problems/height-checker/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1051.java) | O(nlogn) | O(1) | |Easy||
3131
|1047|[Remove All Adjacent Duplicates In String](https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1047.java) | O(n) | O(1) | |Easy||
32+
|1038|[Binary Search Tree to Greater Sum Tree](https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1038.java) | O(n) | O(n) | |Medium|DFS, tree|
3233
|1037|[Valid Boomerang](https://leetcode.com/problems/valid-boomerang/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1037.java) | O(1) | O(1) | |Easy|Math|
3334
|1033|[Moving Stones Until Consecutive](https://leetcode.com/problems/moving-stones-until-consecutive/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1033.java) | O(1) | O(1) | |Easy|Math|
3435
|1030|[Matrix Cells in Distance Order](https://leetcode.com/problems/matrix-cells-in-distance-order/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1030.java) | O(R*C) | O(1) | |Easy|

‎src/main/java/com/fishercoder/solutions/_1038.java

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
package com.fishercoder.solutions;
2+
3+
import com.fishercoder.common.classes.TreeNode;
4+
5+
/**
6+
* 1038. Binary Search Tree to Greater Sum Tree
7+
*
8+
* Given the root of a binary search tree with distinct values,
9+
* 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.
10+
* As a reminder, a binary search tree is a tree that satisfies these constraints:
11+
*
12+
* The left subtree of a node contains only nodes with keys less than the node's key.
13+
* The right subtree of a node contains only nodes with keys greater than the node's key.
14+
* Both the left and right subtrees must also be binary search trees.
15+
*
16+
*
17+
* Example 1:
18+
* 4(30)
19+
* / \
20+
* 1(36) 6(21)
21+
* / \ / \
22+
* 0(36) 2(35) 5(26) 7(15)
23+
* \ \
24+
* 3(33) 8(8)
25+
*
26+
* Input: [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
27+
* Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
28+
*
29+
*
30+
* Note:
31+
*
32+
* The number of nodes in the tree is between 1 and 100.
33+
* Each node will have value between 0 and 100.
34+
* The given tree is a binary search tree.*/
35+
public class _1038 {
36+
public static class Solution1 {
37+
/**credit: https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/discuss/286725/JavaC%2B%2BPython-Revered-Inorder-Traversal*/
38+
int greaterSum = 0;
39+
public TreeNode bstToGst(TreeNode root) {
40+
if (root.right != null) {
41+
bstToGst(root.right);
42+
}
43+
greaterSum = root.val = greaterSum + root.val;
44+
if (root.left != null) {
45+
bstToGst(root.left);
46+
}
47+
return root;
48+
}
49+
}
50+
}

‎src/test/java/com/fishercoder/_1038Test.java

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.common.classes.TreeNode;
4+
import com.fishercoder.common.utils.TreeUtils;
5+
import com.fishercoder.solutions._1038;
6+
import org.junit.BeforeClass;
7+
import org.junit.Test;
8+
9+
import java.util.Arrays;
10+
11+
import static org.junit.Assert.assertEquals;
12+
13+
public class _1038Test {
14+
private static _1038.Solution1 solution1;
15+
private static TreeNode root;
16+
private static TreeNode expected;
17+
private static TreeNode actual;
18+
19+
@BeforeClass
20+
public static void setup() {
21+
solution1 = new _1038.Solution1();
22+
}
23+
24+
@Test
25+
public void test1() {
26+
root = TreeUtils.constructBinaryTree(Arrays.asList(4, 1, 6, 0, 2, 5, 7, null, null, null, 3, null, null, null, 8));
27+
TreeUtils.printBinaryTree(root);
28+
expected = TreeUtils.constructBinaryTree(Arrays.asList(30, 36, 21, 36, 35, 26, 15, null, null, null, 33, null, null, null, 8));
29+
TreeUtils.printBinaryTree(expected);
30+
actual = solution1.bstToGst(root);
31+
TreeUtils.printBinaryTree(actual);
32+
assertEquals(expected, actual);
33+
}
34+
35+
}

0 commit comments

Comments
 (0)
0