05 August 2008
给定二叉树的根，其中每个节点都有一个唯一值和一个目标整数 k，返回树中离目标 k 最近的叶节点的值。
最接近叶子意味着在二叉树上经过的最少边数到达树的任何叶子。此外，如果节点没有子节点，则称为叶子节点。
建图然后DFS
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
class Solution {
public int findClosestLeaf(TreeNode root, int k) {
Map<Integer, List<Integer>> map = new HashMap<>();
build(map, root); //build an undirected graph
return map.isEmpty()? root.val : dfs(map, root.val, k, -1)[1];
}
//this method returns [min distance to leaf, leaf value]
private int[] dfs(Map<Integer, List<Integer>> map, int root, int start, int parent){
boolean isLeaf = map.get(start).size() == 1 && start != root;
int[] min = isLeaf? new int[]{0, start} : new int[]{1001, -1};
for (int next : map.get(start)){
if (next == parent) continue; //can't go back to where you came from.
int[] res = dfs(map, root, next, start);
if (min[0] > res[0]) min = res;
}
min[0]++;
return min;
}
private void build(Map<Integer, List<Integer>> map, TreeNode root){
if (root.right != null){
map.computeIfAbsent(root.val, o -> new ArrayList<>()).add(root.right.val);
map.computeIfAbsent(root.right.val, o -> new ArrayList()).add(root.val);
build(map, root.right);
}
if (root.left != null){
map.computeIfAbsent(root.val, o -> new ArrayList<>()).add(root.left.val);
map.computeIfAbsent(root.left.val, o -> new ArrayList()).add(root.val);
build(map, root.left);
}
}
}
BFS
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
class Solution {
/*
1) First, preform DFS on root in order to find the node whose val = k, at the meantime use HashMap to keep record of all back edges from child to parent;
2) Then perform BFS on this node to find the closest leaf node.
*/
public int findClosestLeaf(TreeNode root, int k) {
Map<TreeNode, TreeNode> backMap = new HashMap<>(); // store all edges that trace node back to its parent
Queue<TreeNode> queue = new LinkedList<>(); // the queue used in BFS
Set<TreeNode> visited = new HashSet<>(); // store all visited nodes
// DFS: search for node whoes val == k
TreeNode kNode = DFS(root, k, backMap);
queue.add(kNode);
visited.add(kNode);
// BFS: find the shortest path
while(!queue.isEmpty()) {
TreeNode curr = queue.poll();
if(curr.left == null && curr.right == null) {
return curr.val;
}
if(curr.left != null && visited.add(curr.left)) {
queue.add(curr.left);
}
if(curr.right != null && visited.add(curr.right)) {
queue.add(curr.right);
}
if(backMap.containsKey(curr) && visited.add(backMap.get(curr))) { // go alone the back edge
queue.add(backMap.get(curr));
}
}
return -1; // never hit
}
private TreeNode DFS(TreeNode root, int k, Map<TreeNode, TreeNode> backMap) {
if(root.val == k) {
return root;
}
if(root.left != null) {
backMap.put(root.left, root); // add back edge
TreeNode left = DFS(root.left, k, backMap);
if(left != null) return left;
}
if(root.right != null) {
backMap.put(root.right, root); // add back edge
TreeNode right = DFS(root.right, k, backMap);
if(right != null) return right;
}
return null;
}
}