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

Commita4f60ed

Browse files
committed
Added 3 solutions
1 parentf2eddae commita4f60ed

File tree

3 files changed

+107
-15
lines changed

3 files changed

+107
-15
lines changed

‎Easy/Two Sum IV - Input is a BST.java

Lines changed: 33 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -8,15 +8,42 @@
88
* }
99
*/
1010
classSolution {
11-
Set<Integer>set =newHashSet<>();
1211
publicbooleanfindTarget(TreeNoderoot,intk) {
13-
if (root ==null)returnfalse;
14-
if (set.contains(k -root.val)) {
15-
returntrue;
12+
Stack<TreeNode>stack =newStack<>();
13+
while (root !=null) {
14+
stack.push(root);
15+
root =root.left;
1616
}
1717

18-
set.add(root.val);
18+
Set<Integer>set =newHashSet<>();
19+
intmin =popStack(stack);
20+
set.add(min);
1921

20-
returnfindTarget(root.right,k) ||findTarget(root.left,k);
22+
while (!stack.isEmpty()) {
23+
intnum =popStack(stack);
24+
if (set.contains(k-num)) {
25+
returntrue;
26+
}
27+
28+
if (min +num >k) {
29+
returnfalse;
30+
}
31+
32+
set.add(num);
33+
}
34+
35+
returnfalse;
36+
}
37+
38+
privateintpopStack(Stack<TreeNode>stack) {
39+
TreeNoden =stack.pop();
40+
TreeNoderight =n.right;
41+
42+
while (right !=null) {
43+
stack.push(right);
44+
right =right.left;
45+
}
46+
47+
returnn.val;
2148
}
2249
}
Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* public class TreeNode {
4+
* int val;
5+
* TreeNode left;
6+
* TreeNode right;
7+
* TreeNode(int x) { val = x; }
8+
* }
9+
*/
10+
classSolution {
11+
Map<Integer,List<Integer>>map =newTreeMap<>();
12+
publicList<List<Integer>>verticalOrder(TreeNoderoot) {
13+
List<List<Integer>>ans =newArrayList<>();
14+
updateMap(root,0);
15+
16+
for (intkey :map.keySet()) {
17+
ans.add(map.get(key));
18+
}
19+
20+
returnans;
21+
}
22+
23+
privatevoidupdateMap(TreeNoderoot,intlevel) {
24+
if (root ==null) {
25+
return;
26+
}
27+
28+
Queue<Element>queue =newLinkedList<>();
29+
queue.add(newElement(root,0));
30+
31+
while (!queue.isEmpty()) {
32+
intsize =queue.size();
33+
34+
while (size-- >0) {
35+
Elementtemp =queue.remove();
36+
if (map.containsKey(temp.level)) {
37+
map.get(temp.level).add(temp.node.val);
38+
}
39+
else {
40+
List<Integer>list =newArrayList<>();
41+
list.add(temp.node.val);
42+
map.put(temp.level,list);
43+
}
44+
45+
if (temp.node.left !=null) {
46+
queue.add(newElement(temp.node.left,temp.level-1));
47+
}
48+
49+
if (temp.node.right !=null) {
50+
queue.add(newElement(temp.node.right,temp.level+1));
51+
}
52+
}
53+
}
54+
}
55+
}
56+
57+
classElement {
58+
publicTreeNodenode;
59+
publicintlevel;
60+
61+
publicElement(TreeNodenode,intlevel) {
62+
this.node =node;
63+
this.level =level;
64+
}
65+
}

‎Medium/Maximum Binary Tree.java

Lines changed: 9 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -9,29 +9,29 @@
99
*/
1010
classSolution {
1111
publicTreeNodeconstructMaximumBinaryTree(int[]nums) {
12-
if (nums ==null)returnnull;
13-
returnconstructMaximumBinaryTreeImpl(nums,0,nums.length-1);
12+
if (nums.length ==0) {
13+
returnnull;
14+
}
15+
16+
returnconstructTree(nums,0,nums.length-1);
1417
}
1518

16-
publicTreeNodeconstructMaximumBinaryTreeImpl(int[]nums,intstart,intend) {
17-
19+
privateTreeNodeconstructTree(int[]nums,intstart,intend) {
1820
if (start >end) {
1921
returnnull;
2022
}
2123

2224
intidx =start;
23-
24-
for (inti =start +1;i <=end;i++) {
25+
for (inti=start+1;i<=end;i++) {
2526
if (nums[i] >nums[idx]) {
2627
idx =i;
2728
}
2829
}
2930

3031
TreeNoderoot =newTreeNode(nums[idx]);
3132

32-
root.left =constructMaximumBinaryTreeImpl(nums,start,idx-1);
33-
34-
root.right =constructMaximumBinaryTreeImpl(nums,idx+1,end);
33+
root.left =constructTree(nums,start,idx-1);
34+
root.right =constructTree(nums,idx+1,end);
3535

3636
returnroot;
3737
}

0 commit comments

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