|
这题跟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;. visit 1point3acres.com for more.
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”是主函数. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
- // Tree node
. visit 1point3acres.com for more. - struct Node {
- int val;
- Node* left, *right;
- // paths: all paths from this node to any descendant
- // multimap: path sum -> path nodes (including single this node path)
- unordered_multimap<int,vector<Node*>> paths;
- Node(int v):val(v),left(NULL),right(NULL){}
- };. 鍥磋鎴戜滑@1point 3 acres
- // result to store all paths with target sum
- vector<vector<Node*>> res;
- // calculate all paths with target sum
- // do post-order traversal
- vector<vector<Node*>> allPaths(Node* r, int t) {. Waral 鍗氬鏈夋洿澶氭枃绔,
- if (!r) return res;
- // calculate target paths in left trees. more info on 1point3acres.com
- auto lres = allPaths(r->left, t);
- // calculate target paths in right trees
- auto rres = allPaths(r->right, t);
- // calculate target paths passing root
- pathsThroughRoot(r, t);
- // combine all paths into result
- res.insert(lres.begin(), lres.end());. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
- res.insert(rres.begin(), rres.end());
- return res;
- }
- // calculate all paths with target sum that pass through node "r"
- void pathsThroughRoot(Node* r, int t) {
- if (!r) return;. more info on 1point3acres.com
- auto rl = r->left, rr = r->right; int rv = r->val;
- // if "r" is a leaf, set the only trivial path.鐣欏璁哄潧-涓浜-涓夊垎鍦
- // and push to result if matching target sum. From 1point 3acres bbs
- if (!rl && !rr) {
- r->paths = {{rv, {r}}};
- if (rv == t) res.push_back({r});
- return;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
- }
- // lpaths: all paths from node "r" to any left descendent (including self)
- unordered_multimap<int,vector<Node*>> lpaths = {{rv, {r}}},
- rpaths = {{rv, {r}}};
- if (rl)
- for (auto& p:rl->paths) {
- vector<Node*> path = {r};
- path.insert(path.end(),p.second.begin(),p.second.end());
- lpath.emplace(rv+p.first,path);
- }
- // rpaths: all paths from node "r" to any right descendent (including self)
- if (rr)
- for (auto& p:rr->paths) {
- vector<Node*> path = {r};
- path.insert(path.end(),p.second.begin(),p.second.end());
- rpath.emplace(rv+p.first,path);
- }
- // combine lpaths and rpath to get r->paths (remove duplicated {r})
- r->paths = lpaths;
- r->paths.insert(r->paths.end(),rpath.begin()+1,rpath.end());
-
- // push paths with target sum to result if there is any. from: 1point3acres.com/bbs
- for (auto& lp:lpaths) {
- for (auto& rp:rpaths) {
- if (lp.first+rp.first == t+rv) { // node "r" is duplicated
- // build path from left tree going through "r" to right tree
- vector<Node*> path = lp.second;
- reverse(path.begin(), path.end());
- path.insert(path.end(), rp.begin()+1, rp.end());
- res.push_back(path);
- }
- } . From 1point 3acres bbs
- }
- }
复制代码
补充内容 (2016-10-23 13:15):. From 1point 3acres bbs
"如何计算经过某个node的所有target sum paths"是指这个node一定是该路径所有nodes的ancestor。这样路径就以该node分成了3部分,使总和match到target sum. |
|