Đường dẫn Sum III trong C ++

Giả sử chúng ta đã đưa ra một cây nhị phân trong đó mỗi nút giữ một khóa số nguyên. Chúng ta phải tìm các đường dẫn đến một giá trị nhất định. Đường đi nên bắt đầu từ gốc đến lá. Chúng ta phải tìm đường dẫn có tổng bằng nhau.

Nếu cây giống như [5,4,8,11, null, 13,4,7,2, null, null, 5,1] và tổng là 22, thì nó sẽ là -

Các đường dẫn là [[5,4,11,2], [5,8,4,5]].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Sử dụng hàm dfs để giải quyết vấn đề này, dfs được sửa đổi một chút, điều này sẽ hoạt động như sau. Hàm này sẽ lấy gốc, tổng và một mảng tạm thời
• nếu root không có mặt, hãy trả về
• nếu bên trái của thư mục gốc và bên phải của thư mục gốc trống, thì
  • nếu sum =giá trị của gốc, thì
    • chèn giá trị của gốc vào tạm thời, chèn tạm thời vào kết quả và xóa nút cuối cùng khỏi tạm thời
  • trở lại
• chèn giá trị của root vào tạm thời
• dfs (bên trái của gốc, tổng - giá trị của gốc, tạm thời)
• dfs (bên phải gốc, tổng - giá trị của gốc, tạm thời)
• xóa phần tử cuối cùng khỏi tạm thời

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<int> > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
class TreeNode{
   public:
      int val;
      TreeNode *left, *right;
      TreeNode(int data){
         val = data;
         left = right = NULL;
      }
};
void insert(TreeNode **root, int val){
      queue<TreeNode*> q;
      q.push(*root);
      while(q.size()){
         TreeNode *temp = q.front();
         q.pop();
         if(!temp->left){
            if(val != NULL)
               temp->left = new TreeNode(val);
            else
               temp->left = new TreeNode(0);
            return;
      } else {
         q.push(temp->left);
      }
      if(!temp->right){
         if(val != NULL)
         temp->right = new TreeNode(val);
         else
            temp->right = new TreeNode(0);
         return;
      } else {
         q.push(temp->right);
      }
   }
}
TreeNode *make_tree(vector<int> v){
   TreeNode *root = new TreeNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   }
   return root;
}
class Solution {
   public:
   vector < vector <int> > res;
   void dfs(TreeNode* root, int sum, vector <int>& temp){
      if(!root)return;
      if(!root->left && !root->right){
         if(sum == root->val){
            temp.push_back(root->val);
            res.push_back(temp);
            temp.pop_back();
         }
         return;
      }
      temp.push_back(root->val);
      dfs(root->left, sum - root->val, temp);
      dfs(root->right, sum - root->val, temp);
      temp.pop_back();
   }
   vector<vector<int>> pathSum(TreeNode* root, int sum) {
      res.clear();
      vector <int> temp;
      dfs(root, sum, temp);
      return res;
   }
};
main(){
   Solution ob;
   vector<int> v = {5,4,8,11,NULL,13,4,7,2,NULL,NULL,NULL,NULL,5,1};
   TreeNode *root = make_tree(v);
   print_vector(ob.pathSum(root, 22));
}

Đầu vào

[5,4,8,11,null,13,4,7,2,null,null,5,1]
22

Đầu ra

[[5, 4, 11, 2, ],[5, 8, 4, 5, ],]