代朋友报一个G家电面面经，醉了

我朋友今天面的，真是醉了，题是Given a binary tree, find the path which nodes sum to a given value. The path can start from and end with any nodes
做过cc150的肯定觉得这个是那上面的原题，但你仔细看CC150的解法，它的最后的答案还是从上到下的这种PATH，也就是从某个祖先（虽然不是ROOT），到某个后代节点

但这个面试官让我朋友做的是真正的可以从任何点开始和结束，也就是说，可以是一个节点，一直网上爬到某个祖先的然后再拐到另外一个孩子往下爬到某个后代这种路径

我朋友说他完全不会，讨论了45分钟还没讨论出正确算法，估计跪了


补充内容 (2016-10-8 11:06):
发现G家面试真是要看RP，很容易碰到各种难偏怪

如果对复杂度没有特别要求其实写起来还好。。。对任意节点求左子为起点的所有sum，和右子为起点的所有sum，两个与root val做combination，看有没有解，然后合并两个sun的list再加root val返回作为以该点为起点的所有sum和，做一个list返回，递归调用。。。大概这样吧

感觉可以在每个节点记录从所有子孙后辈节点到当前的和 看是否有值或者和值为目标值

这个题也有，这个是hard题 对店面来说过于难了

pancymon 发表于 2016-10-8 12:06
这个题也有，这个是hard题 对店面来说过于难了

哪有答案？

pancymon 发表于 2016-10-8 12:06
这个题也有，这个是hard题 对店面来说过于难了

我看LC上有一个任意点起，任意点结束求最大SUM的，但没有说等于特定SUM的

最优解不会的话，暴力穷举总应该会写吧。

三种情况 左子树有 右子树有 不然就肯定经过当前root 对从左节点的出发所以可能的path找右子树有没有这样的对应的值的path 这样好像复杂度挺高 但是如果有规定都是positive可以提前终止就比较好一点 感觉还是太笨拙了这方法

liurudahai 发表于 2016-10-8 12:31
我看LC上有一个任意点起，任意点结束求最大SUM的，但没有说等于特定SUM的

对的.求最大而且没有说打印path...假如只是找存在不存在也差不多.但是要打出来存在的那个路径...怎么存呢？

dexter 发表于 2016-10-8 14:00
对的.求最大而且没有说打印path...假如只是找存在不存在也差不多.但是要打出来存在的那个路径...怎么存呢 ...

能判断存不存在解就能找到解，只不过需要消耗更大的空间复杂度罢了，理论上任何题如果对时间，空间复杂度没要求都能暴力解，只不过写起来麻烦一些，这道题也一样。面试官 出这个题要么就是成心黑人，要么就是不要求bug free 完美解，而更看重思路，但是如果面试时一点思路都没有，那确实差些火候。挂了也说不出什么。

感觉上可以用floyd-warshall去做，tree就相当于graph，每个点到另外点只有一条路径

如果能重构树把树重构成无向图解就行了....dfs....

这个要用Segment tree吧

楼主 这题跟leetcode 124. Binary Tree Maximum Path Sum很类似啊 貌似还简单了点 但是124是hard 所以没看过思路的估计很困难

原题 wrapper class就能解决的

这么简单的题，做不好自己好好回去刷题

配刀老鼠 发表于 2016-10-8 22:13
楼主 这题跟leetcode 124. Binary Tree Maximum Path Sum很类似啊 貌似还简单了点 但是124是hard 所以没看 ...

maximun sum更简单

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x),left(NULL),right(NULL){}
};


multimap<int,vector<TreeNode*> > allPath(TreeNode* root,int target,vector<vector<TreeNode*> >& result){
    multimap<int,vector<TreeNode*> > left_sum,right_sum,root_sum;
    if(root->left)left_sum=allPath(root->left,target,result);
    if(root->right)right_sum=allPath(root->right,target,result);
   
    if(root->val==target)result.push_back(vector<TreeNode*>(1,root));
    root_sum.emplace(root->val,vector<TreeNode*>({root}));
    auto it_left=left_sum.begin();
    auto it_right=right_sum.rbegin();
   
    while(it_left!=left_sum.end() && it_right!=right_sum.rend()){
        while(it_right!=right_sum.rend() && it_left->first+root->val+it_right->first>target)it_right++;
        if(it_right==right_sum.rend())break;
        if(it_left->first+root->val+it_right->first==target){
            vector<TreeNode*> tmp(it_left->second);
            tmp.push_back(root);
            tmp.insert(tmp.end(),it_right->second.rbegin(),it_right->second.rend());
            result.push_back(tmp);
        }
        it_left++;
    }
   
    for(auto p:left_sum){
        p.second.push_back(root);
        root_sum.emplace(root->val+p.first,p.second);
        if(root->val+p.first==target)result.push_back(p.second);
    }
    for(auto p:right_sum){
        p.second.push_back(root);
        root_sum.emplace(root->val+p.first,p.second);
        if(root->val+p.first==target)result.push_back(p.second);
    }
    return root_sum;
}

vector<vector<TreeNode*> > pathSum(TreeNode* root,int target){
    vector<vector<TreeNode*> > result;
    if(!root)return result;
    multimap<int,vector<TreeNode*> > pathes;
   
    allPath(root,target,result);
    return result;
}

edyyy 发表于 2016-10-8 22:29
这么简单的题，做不好自己好好回去刷题

求大神给个解法

这题跟Leetcode 124. Binary Tree Maximum Path Sum很类似，稍有不同。主要思路就是用post-order traversal从leaf node入手来建立从当前node到任意descendent的路径以及总长(sum of value)。因为即使相同总长的路径的nodes也可以不同，所以可以用unordered_multimap<int,vector<Node*>>存储从总长映射到路node的array.
算法概述：
1. 先找出left subtree中所有target sum paths;
2. 再找出right subtree中所有target sum paths;
3. 最后找必须经过root的target sum paths。
4. 合并所有结果到vector<vector<Node*>>中。
核心部分其实就是“3”：如何计算经过某个node的所有target sum paths. 这个很容易利用post-order traversal中已经计算的node->left和node->right的所有到各自任意descendant不同长度的paths来完成。具体code如下，详细注释（没有debug, 但大体算法如下） 。“allPaths”是主函数

1. // Tree node
   
2. struct Node {
   
3.   int val;
   
4.   Node* left, *right;
   
5.   // paths: all paths from this node to any descendant
   
6.   // multimap: path sum -> path nodes (including single this node path)
   
7.   unordered_multimap<int,vector<Node*>> paths;
   
8.   Node(int v):val(v),left(NULL),right(NULL){}
   
9. };
   
10. 
    
11. // result to store all paths with target sum
    
12. vector<vector<Node*>> res;
    
13. 
    
14. // calculate all paths with target sum
    
15. // do post-order traversal
    
16. vector<vector<Node*>> allPaths(Node* r, int t) {
    
17.   if (!r) return res;
    
18.   // calculate target paths in left trees
    
19.   auto lres = allPaths(r->left, t);
    
20.   // calculate target paths in right trees
    
21.   auto rres = allPaths(r->right, t);
    
22.   // calculate target paths passing root
    
23.   pathsThroughRoot(r, t);
    
24.   // combine all paths into result
    
25.   res.insert(lres.begin(), lres.end());
    
26.   res.insert(rres.begin(), rres.end());
    
27.   return res;
    
28. }
    
29. 
    
30. // calculate all paths with target sum that pass through node "r"
    
31. void pathsThroughRoot(Node* r, int t) {
    
32.   if (!r) return;
    
33.   auto rl = r->left, rr = r->right; int rv = r->val;
    
34.   // if "r" is a leaf, set the only trivial path
    
35.   // and push to result if matching target sum
    
36.   if (!rl && !rr) {
    
37.     r->paths = {{rv, {r}}};
    
38.     if (rv == t) res.push_back({r});
    . visit 1point3acres.com for more.
39.     return;
    
40.   }
    
41.   // lpaths: all paths from node "r" to any left descendent (including self)
    
42.   unordered_multimap<int,vector<Node*>> lpaths = {{rv, {r}}},
    
43.     rpaths = {{rv, {r}}};
    
44.   if (rl)
    
45.     for (auto& p:rl->paths) {
    
46.       vector<Node*> path = {r};
    
47.       path.insert(path.end(),p.second.begin(),p.second.end());
    
48.       lpath.emplace(rv+p.first,path);
    
49.     }  
    
50.   // rpaths: all paths from node "r" to any right descendent (including self)   
    
51.   if (rr)
    
52.     for (auto& p:rr->paths) {
    
53.       vector<Node*> path = {r};
    
54.       path.insert(path.end(),p.second.begin(),p.second.end());
    
55.       rpath.emplace(rv+p.first,path);
    
56.     }  
    
57.   // combine lpaths and rpath to get r->paths (remove duplicated {r})
    
58.   r->paths = lpaths;
    
59.   r->paths.insert(r->paths.end(),rpath.begin()+1,rpath.end());
    
60.   
    
61.   // push paths with target sum to result if there is any
    
62.   for (auto& lp:lpaths) {
    
63.     for (auto& rp:rpaths) {
    
64.       if (lp.first+rp.first == t+rv) { // node "r" is duplicated
    
65.         // build path from left tree going through "r" to right tree
    
66.         vector<Node*> path = lp.second;
    
67.         reverse(path.begin(), path.end());
    
68.         path.insert(path.end(), rp.begin()+1, rp.end());
    
69.         res.push_back(path);
    
70.       }      
    
71.     }  
    
72.   }
    
73. }

复制代码

补充内容 (2016-10-23 13:15):
"如何计算经过某个node的所有target sum paths"是指这个node一定是该路径所有nodes的ancestor。这样路径就以该node分成了3部分，使总和match到target sum.