Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitd5218be

Browse files
[LEET-538] add 538
1 parent0c84040 commitd5218be

File tree

3 files changed

+113
-0
lines changed

3 files changed

+113
-0
lines changed

‎leetcode-algorithms/README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@
99
|541|[Reverse String II](https://leetcode.com/problems/reverse-string-ii/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/ReverseStringII.java) | O(n) |O(1) | Easy | String
1010
|540|[Single Element in a Sorted Array](https://leetcode.com/problems/single-element-in-a-sorted-array/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/SingleElementinaSortedArray.java)| O(n)|O(1)| Medium|
1111
|539|[Minimum Time Difference](https://leetcode.com/problems/minimum-time-difference/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/MinimumTimeDifference.java) | O(n) |O(1) | Medium | String
12+
|538|[Convert BST to Greater Tree](https://leetcode.com/problems/convert-bst-to-greater-tree/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/ConvertBSTtoGreaterTree.java) | O(nlogn) |O(n) | Medium | Tree
1213
|536|[Construct Binary Tree from String](https://leetcode.com/problems/construct-binary-tree-from-string/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/ConstructBinaryTreefromString.java) | O(n) |O(h) | Medium | Recursion
1314
|535|[Encode and Decode TinyURL](https://leetcode.com/problems/encode-and-decode-tinyurl/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/EncodeandDecodeTinyURL.java) | O(1) |O(n) | Medium | Design
1415
|532|[K-diff Pairs in an Array](https://leetcode.com/problems/k-diff-pairs-in-an-array/)|[Solution](../../master/leetcode-algorithms/src/main/java/com/stevesun/solutions/KdiffPairsinanArray.java) | O(n) |O(n) | Easy | HashMap
Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
packagecom.stevesun.solutions;
2+
3+
importcom.stevesun.common.classes.TreeNode;
4+
5+
importjava.util.ArrayList;
6+
importjava.util.Collections;
7+
importjava.util.List;
8+
importjava.util.TreeMap;
9+
10+
/**
11+
* Given 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 sum of all keys greater than the original key in BST.
12+
13+
Example:
14+
15+
Input: The root of a Binary Search Tree like this:
16+
5
17+
/ \
18+
2 13
19+
20+
Output: The root of a Greater Tree like this:
21+
18
22+
/ \
23+
20 13
24+
*/
25+
26+
publicclassConvertBSTtoGreaterTree {
27+
//This solution is generic for both BST and regular binary trees
28+
publicTreeNodeconvertBST(TreeNoderoot) {
29+
if (root ==null)returnroot;
30+
List<Integer>list =newArrayList<>();
31+
putNodeToList(list,root);
32+
Collections.sort(list);
33+
int[]sums =newint[list.size()];
34+
sums[list.size()-1] =0;
35+
for (inti =list.size()-2;i >=0;i--) {
36+
sums[i] =sums[i+1] +list.get(i+1);
37+
}
38+
TreeMap<Integer,Integer>treeMap =newTreeMap<>();
39+
for (inti =0;i <list.size();i++) {
40+
treeMap.put(list.get(i),sums[i]);
41+
}
42+
TreeNoderesult =newTreeNode(treeMap.get(list.get(0)));
43+
returngenerateResultRoot(root,treeMap,result);
44+
}
45+
46+
privateTreeNodegenerateResultRoot(TreeNoderoot,TreeMap<Integer,Integer>treeMap,TreeNoderesult) {
47+
if (root !=null)result.val =treeMap.get(root.val) +root.val;
48+
if (root.left !=null) {
49+
result.left =newTreeNode(0);
50+
generateResultRoot(root.left,treeMap,result.left);
51+
}
52+
if (root.right !=null) {
53+
result.right =newTreeNode(0);
54+
generateResultRoot(root.right,treeMap,result.right);
55+
}
56+
returnresult;
57+
}
58+
59+
privatevoidputNodeToList(List<Integer>list,TreeNoderoot) {
60+
if (root !=null)list.add(root.val);
61+
if (root.left !=null)putNodeToList(list,root.left);
62+
if (root.right !=null)putNodeToList(list,root.right);
63+
}
64+
65+
}
Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
packagecom.stevesun;
2+
3+
importcom.stevesun.common.classes.TreeNode;
4+
importcom.stevesun.solutions.ConvertBSTtoGreaterTree;
5+
importorg.junit.Before;
6+
importorg.junit.BeforeClass;
7+
importorg.junit.Test;
8+
9+
importstaticjunit.framework.Assert.assertEquals;
10+
11+
publicclassConvertBSTtoGreaterTreeTest {
12+
privatestaticConvertBSTtoGreaterTreetest;
13+
privatestaticTreeNodeactualRoot;
14+
privatestaticTreeNodeexpectedRoot;
15+
privatestaticTreeNoderoot;
16+
17+
@BeforeClass
18+
publicstaticvoidsetup(){
19+
test =newConvertBSTtoGreaterTree();
20+
}
21+
22+
@Before
23+
publicvoidsetupForEachTest(){
24+
}
25+
26+
@Test
27+
publicvoidtest1(){
28+
root =newTreeNode(5);
29+
root.left =newTreeNode(2);
30+
root.right =newTreeNode(13);
31+
32+
expectedRoot =newTreeNode(18);
33+
expectedRoot.left =newTreeNode(20);
34+
expectedRoot.right =newTreeNode(13);
35+
actualRoot =test.convertBST(root);
36+
assertEquals(expectedRoot.toString(),actualRoot.toString());
37+
}
38+
39+
@Test
40+
publicvoidtest2(){
41+
root =null;
42+
43+
expectedRoot =null;
44+
actualRoot =test.convertBST(root);
45+
assertEquals(expectedRoot,actualRoot);
46+
}
47+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp