黑车公司

binary tree 找所以路径和等于target，打印出来那些paths

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

/strong>
路径不一定从root开始

烙印也不全不好了。我刚过的一个面试就是印度人。挺好的。我fail的都不是烙印，当然从来没遇到过国人。。。尽力做好就好了。心态放宽。很多时候有很多外部因素

1.        
   
2.         private void pathSum(TreeNode root, int sum, int preSum, Map<Integer,
   
3.                         List<Integer>> inds, List<Integer> path, List<List<Integer>> res) {
   
4.                 if (root == null) {
   
5.                         return;
   
6.                 }
   
7.                 int curSum = preSum + root.val;
   
8.                 path.add(root.val);
   
9.                 int toFind = curSum - sum;
   
10.                 if (inds.containsKey(toFind)) {
    
11.                         for (int preInd : inds.get(toFind)) {
    
12.                                 res.add(subArray(path, preInd));
    
13.                         }
    
14.                 }
    
15.                 inds.putIfAbsent(curSum, new ArrayList<Integer>());
    
16.                 inds.get(curSum).add(path.size());
    
17.                 pathSum(root.left, sum, curSum, inds, path, res);
    
18.                 pathSum(root.right, sum, curSum, inds, path, res);
    
19.                 List<Integer> indsList = inds.get(curSum);
    
20.                 if (indsList.size() == 1) {
    
21.                         inds.remove(curSum);
    
22.                 } else {
    
23.                         indsList.remove(indsList.size() - 1);
    
24.                 }
    
25.                 path.remove(path.size() - 1);
    
26.         }
    
27.        
    
28.         private List<Integer> subArray(List<Integer> path, int ind) {
    
29.                 List<Integer> res = new ArrayList<>();
    
30.                 for (int i = ind; i < path.size(); ++i) {
    
31.                         res.add(path.get(i));
    
32.                 }
    
33.                 return res;
    
34.         }

复制代码

补充内容 (2018-7-22 02:59):
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
                Map<Integer, List<Integer>> inds = new HashMap<>();
                inds.put(0, new ArrayList<Integer>());
                inds.get(0).add(0);
                List<Integer> pa...

Timofu 发表于 2018-7-12 10:53
是437， 但是难点是要打印路径

对，打印路径很麻烦

莉蔻一一三？

这题应该是里扣似伞漆， 不一定从根部开始

补充内容 (2018-7-12 08:57):
貌似不太一样，是楼上那题和这题的结合

love_ballon 发表于 2018-7-12 08:50
这题应该是里扣似伞漆， 不一定从根部开始

补充内容 (2018-7-12 08:57):

是437， 但是难点是要打印路径

Timofu 发表于 2018-7-12 10:53
是437， 但是难点是要打印路径

楼主时间内做完了吗? 感觉时间不太够啊...

say543 发表于 2018-7-12 14:43
楼主时间内做完了吗? 感觉时间不太够啊...

做完了，但是不是最优，而且阿三还掐表，整个面试都没够45min他就说到时间了。。体验很差

Timofu 发表于 2018-7-13 00:42
做完了，但是不是最优，而且阿三还掐表，整个面试都没够45min他就说到时间了。。体验很差

适用hashMap<sum, List<List<Integer>>> 这样每个recursive level 一直合并吗 还是有更好的方法? (这是java syntax....)

say543 发表于 2018-7-13 14:52
适用hashMap 这样每个recursive level 一直合并吗 还是有更好的方法? (这是java syntax....)

可以啊，我没有想到更好的方法