https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/description/
863. All Nodes Distance K in Binary Tree
給你一個二元樹的根節點 root，另一個在 root 的節點 target 表示目標節點，以及一
個數字 k ，找出所有距離 target 節點為 k 的節點編號。
（題目的所有節點編號都是獨特的）
Example 1:
https://s3-lc-upload.s3.amazonaws.com/uploads/2018/06/28/sketch0.png
Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [7,4,1]
Explanation: The nodes that are a distance 2 from the target node (with value
5) have values 7, 4, and 1.
Example 2:
Input: root = [1], target = 1, k = 3
Output: []
思路：
1.找距離某個節點為X的所有節點可以用BFS去找，在做之前要先做兩個處理。
2.先找出 target 節點，因為我們要以他為中心進行BFS。
3.把二元樹轉成無向圖，因為二元樹不支持往上遍歷，這樣才可以找target上面的節點
距離。
4.用一個Set來避免無向圖死循環。
5.當BFS的深度為 k 的時候就把節點編號加入結果集。
Java Code：
------------------------------------------------
class Solution {
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
List<Integer> res = new ArrayList<>();
if (k == 0) {
res.add(target.val);
return res;
}
Map<Integer, List<TreeNode>> graph = new HashMap<>();
dfs(root, null, graph);
Set<Integer> visited = new HashSet<>();
Queue<TreeNode> queue = new LinkedList<>();
visited.add(target.val);
for (TreeNode neighbor : graph.get(target.val)) {
queue.offer(neighbor);
}
// BFS
int dis = 1;
while (!queue.isEmpty() && dis <= k) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode curr = queue.poll();
visited.add(curr.val);
if (dis == k) {
res.add(curr.val);
continue;
}
for (TreeNode neighbor : graph.get(curr.val)) {
if (!visited.contains(neighbor.val)) {
queue.offer(neighbor);
}
}
}
dis++;
}
return res;
}
private void dfs(TreeNode root, TreeNode prev, Map<Integer,
List<TreeNode>> graph) {
List<TreeNode> neighbor = new ArrayList<>(3);
graph.put(root.val, neighbor);
if (prev != null) {
neighbor.add(prev);
}
if (root.left != null) {
neighbor.add(root.left);
dfs(root.left, root, graph);
}
if (root.right != null) {
neighbor.add(root.right);
dfs(root.right, root, graph);
}
}
}
------------------------------------------------
我建出來的圖=大變
--
https://i.imgur.com/CBMFmWk.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1689093424.A.A1F.html