863题的DFS 解法，附上代码

这题大家觉得好做吗？  （仅讨论DFS的做法）

我想得头都快炸了。

1. class Solution {
   
2. 
   
3.         Map<TreeNode, Integer> map = new HashMap<>();
   
4.    
   
5.         public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
   
6.             List<Integer> res = new ArrayList<>();
   
7.             find(root, target);
   
8.             search(root, 0, K, res);
   
9.             return res;
   
10.         }
    
11. 
    
12.         private void find(TreeNode root, TreeNode target) {
    
13.             
    
14.             if (root == null) {
    
15.                 return;
    
16.             }
    
17. 
    
18.             if (root == target) {
    
19.                 map.put(root, 0);
    
20.                 return;
    
21.             }
    
22. 
    
23.             find(root.left, target);
    
24.             if (map.containsKey(root.left)) {
    
25.                 map.put(root, map.get(root.left) + 1);
    
26.                 return;
    
27.             }
    
28. 
    
29.             find(root.right, target);
    
30.             if (map.containsKey(root.right)) {
    
31.                 map.put(root, map.get(root.right) + 1);
    
32.                 return;
    
33.             }
    
34.             return;
    
35.             
    
36.         }
    
37. 
    
38.         public void search(TreeNode root, int dis, int K, List<Integer> res) {
    
39.             
    
40.             if (root == null) {
    
41.                 return;
    
42.             }
    
43. 
    
44.             if (map.containsKey(root)) {
    
45.                 dis = map.get(root);
    
46.             }
    
47. 
    
48.             if (dis == K) {
    
49.                 res.add(root.val);
    
50.             }
    
51. 
    
52.             search(root.left, dis + 1, K, res);
    
53.             search(root.right, dis + 1, K, res);
    
54.             
    
55.         }
    
56. }

复制代码

我猜你是卡在search的部分吧?
假設target 是在左子樹, 那每次往右子樹往下的時候distance 都是root distance +1, 這部分沒問題, 因為是離target愈來愈遠, 且find 的過程中所有的右子樹都不會被記錄在map, 這時候dis +1 就會被用到
但在左子樹就不是了
當你往下一層的時候有幾種情況
EX
          1
        2   3
     4  5    6
    7
target = 4
1. 靠近target, node = 2 時, distance = root distance - 1
2. 先靠近target, 再遠離target, 例如node 5 及其子樹
3. 越過target, 距離增加, 例如node 7 及其子樹
因此在左子樹的traverse中, update distance是必要的, 不能單純用dis + 1 來當作距離計算

ashang83 发表于 2020-11-1 08:33
我猜你是卡在search的部分吧?
假設target 是在左子樹, 那每次往右子樹往下的時候distance 都是root distan ...

谢谢同学，我卡的是dfs的 find 部分～～～～ 我觉得这个find太神奇了

techDiscussion 发表于 2020-11-1 08:46
谢谢同学，我卡的是dfs的 find 部分～～～～ 我觉得这个find太神奇了

的確是
利用dfs 先找到target再往回update路徑上所有node的distance, 但又不觸及不需要的node
滿不錯的