-
Notifications
You must be signed in to change notification settings - Fork 5
/
AllNodesDistanceKInBinaryTree.java
64 lines (63 loc) · 1.87 KB
/
AllNodesDistanceKInBinaryTree.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
Map<Integer,List<Integer>> graph;
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
graph = new HashMap<Integer,List<Integer>>();
buildGraph(root,null);
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(target.val);
int level = 0, node, len, i;
boolean flag;
List<Integer> result = new ArrayList<Integer>();
if (k == 0)
{
result.add(target.val);
return result;
}
boolean[] visited = new boolean[501];
while (!queue.isEmpty())
{
flag = false;
len = queue.size();
for (i = 0; i < len; ++i)
{
node = queue.poll();
if (visited[node]) continue;
visited[node] = true;
flag = true;
for (Integer adjNode : graph.get(node))
queue.add(adjNode);
}
if (flag) ++level;
if (level == k)
{
for (Integer elem : queue)
if (!visited[elem])
result.add(elem);
break;
}
}
return result;
}
private void buildGraph(TreeNode node, TreeNode parent)
{
if (node == null) return;
if (!graph.containsKey(node.val)) graph.put(node.val,new ArrayList<Integer>());
if (parent != null)
{
graph.get(parent.val).add(node.val);
graph.get(node.val).add(parent.val);
}
buildGraph(node.left,node);
buildGraph(node.right,node);
}
}