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

Commit0a3d891

Browse files
committed
[Function add]
1. Add leetcode solutions with amazon tag.
1 parentb853d27 commit0a3d891

File tree

3 files changed

+122
-1
lines changed

3 files changed

+122
-1
lines changed

‎leetcode/333. Largest BST Subtree.md

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
##333. Largest BST Subtree
2+
3+
###Question
4+
Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.
5+
6+
Note:
7+
A subtree must include all of its descendants.
8+
9+
```
10+
Example:
11+
12+
Input: [10,5,15,1,8,null,7]
13+
14+
10
15+
/ \
16+
5 15
17+
/ \ \
18+
1 8 7
19+
20+
Output: 3
21+
Explanation: The Largest BST Subtree in this case is the highlighted one.
22+
The return value is the subtree's size, which is 3.
23+
```
24+
25+
Follow up:
26+
Can you figure out ways to solve it with O(n) time complexity?
27+
28+
###Solution:
29+
* Method 1: recursion, bottom to top
30+
1. There are 4 necessary parameters to return.
31+
2. 0: isBST, 1: min, 2: max, 3: number of nodes
32+
```Java
33+
/**
34+
* Definition for a binary tree node.
35+
* public class TreeNode {
36+
* int val;
37+
* TreeNode left;
38+
* TreeNode right;
39+
* TreeNode(int x) { val = x; }
40+
* }
41+
*/
42+
class Solution {
43+
public int largestBSTSubtree(TreeNode root) {
44+
if(root == null) return 0;
45+
int[] res = helper(root);
46+
return res[3];
47+
}
48+
private int[] helper(TreeNode node){// 0: isBST, 1: min, 2: max, 3: number of nodes
49+
int[] left = new int[]{1, node.val, node.val, 0};
50+
int[] right = new int[]{1, node.val, node.val, 0};
51+
if(node.left != null) left = helper(node.left);
52+
if(node.right != null) right = helper(node.right);
53+
boolean isBST = left[0] == 1
54+
&& right[0] == 1
55+
&& (node.left != null ? node.val > left[2]: true)
56+
&& (node.right != null ? node.val < right[1]: true);
57+
int number = isBST ? 1 + left[3] + right[3] : Math.max(left[3], right[3]);
58+
return new int[]{isBST ? 1: 0, left[1], right[2], number};
59+
}
60+
}
61+
```

‎leetcode/508. Most Frequent Subtree Sum.md

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -73,3 +73,48 @@ Note: You may assume the sum of values in any subtree is in the range of 32-bit
7373
}
7474
}
7575
```
76+
77+
###Amazon Session
78+
* Method 1: recursion, bottom to top
79+
```Java
80+
/**
81+
* Definition for a binary tree node.
82+
* public class TreeNode {
83+
* int val;
84+
* TreeNode left;
85+
* TreeNode right;
86+
* TreeNode(int x) { val = x; }
87+
* }
88+
*/
89+
class Solution {
90+
private Map<Integer, Integer> map;
91+
public int[] findFrequentTreeSum(TreeNode root) {
92+
if(root == null) return new int[0];
93+
this.map = new HashMap<>();
94+
dfs(root);
95+
int max = 0, count = 0;
96+
for(int freq : map.values()){
97+
if(freq > max){
98+
count = 1;
99+
max = freq;
100+
}else if(freq == max) count++;
101+
}
102+
int[] res = new int[count];
103+
int index = 0;
104+
for(Map.Entry<Integer, Integer> entry: map.entrySet()){
105+
if(entry.getValue() == max){
106+
res[index++] = entry.getKey();
107+
}
108+
}
109+
return res;
110+
}
111+
private int dfs(TreeNode node){
112+
int left = 0, right = 0;
113+
if(node.left != null) left = dfs(node.left);
114+
if(node.right != null) right = dfs(node.right);
115+
int sum = left + right + node.val;
116+
map.put(sum, map.getOrDefault(sum, 0) + 1);
117+
return sum;
118+
}
119+
}
120+
```

‎leetcode/55. Jump Game.md

Lines changed: 16 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -61,4 +61,19 @@ class Solution {
6161
returntrue;
6262
}
6363
}
64-
```
64+
```
65+
66+
###Amazon session
67+
* Method 1: Greedy
68+
```Java
69+
class Solution {
70+
public boolean canJump(int[] nums) {
71+
int max = 0;
72+
for(int i = 0; i < nums.length; i++){
73+
if(max < i) return false;
74+
max = Math.max(max, i + nums[i]);
75+
}
76+
return true;
77+
}
78+
}
79+
```

0 commit comments

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