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

Commit60a6f1e

Browse files
committed
[Function add]
1. Add leetcode solutions with tag amazon.
1 parentfbcbf2f commit60a6f1e

3 files changed

+161
-2
lines changed

‎leetcode/314. Binary Tree Vertical Order Traversal.md

Lines changed: 47 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -163,4 +163,50 @@ Output:
163163
return result;
164164
}
165165
}
166-
```
166+
```
167+
168+
###Amazon session
169+
* Method 1: dfs + TreeMap
170+
```Java
171+
/**
172+
* Definition for a binary tree node.
173+
* public class TreeNode {
174+
* int val;
175+
* TreeNode left;
176+
* TreeNode right;
177+
* TreeNode(int x) { val = x; }
178+
* }
179+
*/
180+
class Solution {
181+
// key: colNum, value: (key: rowNum, value: node values)
182+
private TreeMap<Integer, TreeMap<Integer, List<Integer>>> map;
183+
public List<List<Integer>> verticalOrder(TreeNode root) {
184+
this.map = new TreeMap<>();
185+
List<List<Integer>> result = new ArrayList<>();
186+
if(root == null) return result;
187+
// use recursion to add nodes to tree map.
188+
dfs(0, 0, root);
189+
// add to result;
190+
for(TreeMap<Integer, List<Integer>> out: map.values()){
191+
List<Integer> list = new ArrayList<>();
192+
for(List<Integer> value: out.values()){
193+
list.addAll(value);
194+
}
195+
result.add(list);
196+
}
197+
return result;
198+
}
199+
private void dfs(int x, int y, TreeNode node){
200+
if(node == null) return;
201+
else{
202+
TreeMap<Integer, List<Integer>> cur = map.getOrDefault(y, new TreeMap<>());
203+
List<Integer> list = cur.getOrDefault(x, new ArrayList<>());
204+
list.add(node.val);
205+
cur.put(x, list);
206+
map.put(y, cur);
207+
dfs(x + 1, y - 1, node.left);
208+
dfs(x + 1, y + 1, node.right);
209+
}
210+
}
211+
}
212+
```

‎leetcode/545. Boundary of Binary Tree.md

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -104,4 +104,50 @@ So order them in anti-clockwise without duplicate nodes we have [1,2,4,7,8,9,10,
104104
if(node.right != null) dfs(node.right, list);
105105
}
106106
}
107+
```
108+
109+
###Amazon Session
110+
* Method 1: DFS
111+
```Java
112+
/**
113+
* Definition for a binary tree node.
114+
* public class TreeNode {
115+
* int val;
116+
* TreeNode left;
117+
* TreeNode right;
118+
* TreeNode(int x) { val = x; }
119+
* }
120+
*/
121+
class Solution {
122+
List<Integer> result;
123+
public List<Integer> boundaryOfBinaryTree(TreeNode root) {
124+
this.result = new ArrayList<>();
125+
if(root == null) return this.result;
126+
result.add(root.val);
127+
dfsLeft(root.left);
128+
dfsLeaves(root.left);
129+
dfsLeaves(root.right);
130+
dfsRight(root.right);
131+
return result;
132+
}
133+
private void dfsLeft(TreeNode node){
134+
if(node == null || (node.left == null && node.right == null)) return;
135+
result.add(node.val);
136+
dfsLeft(node.left == null ? node.right: node.left);
137+
}
138+
private void dfsRight(TreeNode node){
139+
if(node == null || (node.left == null && node.right == null)) return;
140+
dfsRight(node.right == null ? node.left: node.right);
141+
result.add(node.val);
142+
}
143+
private void dfsLeaves(TreeNode node){
144+
if(node == null) return;
145+
else if(node.left == null && node.right == null){
146+
this.result.add(node.val);
147+
return;
148+
}
149+
dfsLeaves(node.left);
150+
dfsLeaves(node.right);
151+
}
152+
}
107153
```

‎leetcode/863. All Nodes Distance K in Binary Tree.md

Lines changed: 68 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -88,4 +88,71 @@ Note:
8888
graph.put(node, neighbours);
8989
}
9090
}
91-
```
91+
```
92+
93+
###Amazon session
94+
*Method1: dfs+ bfs
95+
```Java
96+
/**
97+
* Definition for a binary tree node.
98+
* public class TreeNode {
99+
* int val;
100+
* TreeNode left;
101+
* TreeNode right;
102+
* TreeNode(int x) { val = x; }
103+
* }
104+
*/
105+
classSolution {
106+
privateMap<TreeNode,List<TreeNode>> g;
107+
publicList<Integer>distanceK(TreeNoderoot,TreeNodetarget,intK) {
108+
g=newHashMap<>();
109+
List<Integer> result=newArrayList<>();
110+
dfs(root);// create a graph
111+
Queue<TreeNode> q=newLinkedList<>();
112+
q.offer(target);
113+
int level=0;
114+
Set<TreeNode> visited=newHashSet<>();
115+
visited.add(target);
116+
while(!q.isEmpty()&& level<K){
117+
int size= q.size();
118+
for(int sz=0; sz< size; sz++){
119+
TreeNode cur= q.poll();
120+
if(g.containsKey(cur)){
121+
List<TreeNode> neighbours= g.get(cur);
122+
for(TreeNode n: neighbours){
123+
if(!visited.contains(n)){
124+
visited.add(n);
125+
q.offer(n);
126+
}
127+
}
128+
}
129+
}
130+
level++;
131+
}
132+
if(level==K){
133+
for(TreeNode n: q){
134+
result.add(n.val);
135+
}
136+
}
137+
return result;
138+
}
139+
privatevoiddfs(TreeNodenode){
140+
List<TreeNode> neighbours= g.getOrDefault(node,newArrayList<>());
141+
if(node.left!=null){
142+
neighbours.add(node.left);
143+
List<TreeNode> lefts= g.getOrDefault(node.left,newArrayList<>());
144+
lefts.add(node);
145+
g.put(node.left, lefts);
146+
dfs(node.left);
147+
}
148+
if(node.right!=null){
149+
neighbours.add(node.right);
150+
List<TreeNode> rights= g.getOrDefault(node.right,newArrayList<>());
151+
rights.add(node);
152+
g.put(node.right, rights);
153+
dfs(node.right);
154+
}
155+
g.put(node, neighbours);
156+
}
157+
}
158+
```

0 commit comments

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