Commitdc4ab5d

authored

Create 863-All-Nodes-Distance-K-in-Binary-Tree.java

1 parenta664117 commitdc4ab5dCopy full SHA for dc4ab5d

File tree

+49

-0

lines changed

+49

-0

lines changed

Lines changed: 49 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,49 @@`
	`1`	`+//Just store the value for parent values in a map and just do bfs as we do in graph.`
	`2`	`+`
	`3`	`+classSolution {`
	`4`	`+publicList<Integer>distanceK(TreeNoderoot,TreeNodetarget,intk) {`
	`5`	`+HashMap<TreeNode,TreeNode>map =newHashMap<>();`
	`6`	`+//First bfs to make a mapping to the parent nodes`
	`7`	`+Queue<TreeNode>q1 =newLinkedList<>();`
	`8`	`+q1.offer(root);`
	`9`	`+while (!q1.isEmpty()) {`
	`10`	`+intsize =q1.size();`
	`11`	`+for (inti =0;i<size;i++) {`
	`12`	`+TreeNodecur =q1.poll();`
	`13`	`+if(cur.left!=null) {`
	`14`	`+q1.offer(cur.left);`
	`15`	`+map.put(cur.left,cur);`
	`16`	`+ }`
	`17`	`+if (cur.right!=null) {`
	`18`	`+q1.offer(cur.right);`
	`19`	`+map.put(cur.right,cur);`
	`20`	`+ }`
	`21`	`+ }`
	`22`	`+ }`
	`23`	`+Queue<TreeNode>q2 =newLinkedList<>();`
	`24`	`+HashSet<TreeNode>vis =newHashSet<>();`
	`25`	`+List<Integer>ans =newArrayList<>();`
	`26`	`+intdis =0;`
	`27`	`+q2.offer(target);`
	`28`	`+while (!q2.isEmpty()) {`
	`29`	`+intsize =q2.size();`
	`30`	`+for (inti =0;i<size;i++) {`
	`31`	`+TreeNodecur =q2.poll();`
	`32`	`+if (!vis.contains(cur)) {`
	`33`	`+if (cur.left!=null)`
	`34`	`+q2.offer(cur.left);`
	`35`	`+if (cur.right!=null)`
	`36`	`+q2.offer(cur.right);`
	`37`	`+if (map.get(cur)!=null)`
	`38`	`+q2.offer(map.get(cur));`
	`39`	`+if (dis==k) {`
	`40`	`+ans.add(cur.val);`
	`41`	`+ }`
	`42`	`+ }`
	`43`	`+vis.add(cur);`
	`44`	`+ }`
	`45`	`+dis++;`
	`46`	`+ }`
	`47`	`+returnans;`
	`48`	`+ }`
	`49`	`+}`

Comments

(0)