fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>
  4. using namespace std;
  5.  
  6. // const int maxn = 100;
  7. struct Node{
  8.     int val;
  9.     Node *left, *right, *parent;
  10.     Node(int val) : left(NULL), right(NULL), parent(NULL), val(val) { }
  11. };
  12.  
  13.  
  14.  
  15. Node* createTree(){
  16.   Node* root=new Node(1);
  17.   //level 2
  18.   root->left=new Node(2);
  19.   root->right=new Node(3);
  20.   //level 3
  21.   root->left->left=new Node(2);
  22.   root->left->right=new Node(2);
  23.   root->right->left=new Node(3);
  24.   return root;
  25. }
  26.  
  27.  
  28. vector< vector<int> >  combineTrees(vector<vector<int> >& v1, vector<vector<int> >& v2, vector<vector<int> >& v3 ){
  29.     v1.insert(v1.end(), v2.begin(), v2.end());
  30.     v1.insert(v1.end(), v3.begin(), v3.end());
  31.     return v1;
  32. }
  33.  
  34.  
  35. vector<vector<int> > find_all_trees(Node* root){
  36.     vector<vector<int> > v;
  37.  
  38.     if(NULL==root) return v;
  39.  
  40.  
  41.     vector<vector<int> > left_all_trees=find_all_trees(root->left);
  42.     vector<vector<int> > right_all_trees=find_all_trees(root->right);
  43.  
  44.  
  45.     vector<int> singleV; 
  46.     singleV.push_back(root->val); 
  47.     v.push_back(singleV);
  48.  
  49.     if(left_all_trees.size()==0 && right_all_trees.size()==0 ){
  50.         return v;
  51.     }
  52.  
  53.  
  54.  
  55.  
  56.     vector< vector<int>> leftTrees;
  57.     vector< vector<int>> rightTrees;
  58.     vector< vector<int>> crossTrees;
  59.  
  60.     for (auto& left : left_all_trees ){
  61.         vector<int> leftTree=left;
  62.         leftTree.push_back(root->val);
  63.         leftTrees.push_back(leftTree);
  64.     }
  65.  
  66.     for (auto& right : right_all_trees){
  67.         vector<int> rightTree=right;
  68.         rightTree.push_back(root->val);
  69.         rightTrees.push_back(rightTree);
  70.     }
  71.  
  72.     for(auto& left: left_all_trees)
  73.       for (auto& right: right_all_trees) {
  74.           vector<int> crossTree=left;
  75.           crossTree.push_back(root->val);
  76.           for (auto& item : right){
  77.             crossTree.push_back(item);
  78.           }
  79.           crossTrees.push_back(crossTree);
  80.       }
  81.  
  82.       vector< vector<int> > allTrees= combineTrees(leftTrees, rightTrees, crossTrees);
  83.       allTrees.push_back(singleV);
  84.       return allTrees;
  85. }
  86.  
  87.  
  88.  
  89. int treeSum(const vector<int>& v){
  90.     int sum=0;
  91.     for (auto& item: v){
  92.       sum +=item;
  93.     }
  94.     return sum;
  95. }
  96.  
  97.  
  98. vector<vector<int> > find_sum(Node* root, int target){
  99.  
  100.     vector<vector<int> > pathTrees;  
  101.  
  102.     if(NULL==root) 
  103.         return pathTrees;
  104.  
  105.     vector<vector<int> > trees = find_all_trees(root);
  106.     vector<vector<int> > leftSumTrees=find_sum(root->left, target);
  107.     vector<vector<int> > rightSumTrees=find_sum(root->right, target);
  108.  
  109.     for (int i = 0; i < trees.size(); ++i){
  110.         if( treeSum(trees[i]) ==target ){
  111.             pathTrees.push_back(trees[i]);
  112.         }   
  113.     }
  114.  
  115.     return combineTrees(pathTrees,leftSumTrees, rightSumTrees)  ;
  116.  }
  117.  
  118.  
  119.  
  120. int main(){
  121.     Node* root=createTree();
  122.     vector<vector<int> > v=find_sum(root, 6);
  123.     for (auto& vectorItem : v){
  124.         cout<<" list of item ";
  125.         for (auto& item : vectorItem){
  126.            cout<<item<<" ";
  127.         }
  128.         cout<<endl;
  129.     }
  130.  
  131.     return 0;
  132. }
Success #stdin #stdout 0s 3480KB
comments (?)
stdin 
Standard input is empty
stdout 
 list of item 2 1 3 
 list of item 2 2 2 
 list of item 3 3
https://ideone.com/FQgiU8
tree sum from any node
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!