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

Giả sử chúng ta có một danh sách các số nguyên đại diện cho một cây nhị phân có độ sâu nhỏ hơn 5. Nếu độ sâu của một cây nhỏ hơn 5, thì cây này có thể được biểu diễn bằng một danh sách các số nguyên có ba chữ số. Đối với mỗi số nguyên trong danh sách này -

• Chữ số hàng trăm thể hiện độ sâu D của nút này, 1 <=D <=4.

• Chữ số hàng chục đại diện cho vị trí P của nút này ở mức mà nó thuộc trong phạm vi, 1 đến 8. Vị trí giống như vị trí trong cây nhị phân đầy đủ.

• Chữ số hàng đơn vị được sử dụng để biểu thị giá trị V của nút này, 0 <=V <=9.

Chúng ta phải tìm tổng tất cả các đường đi từ gốc đến lá.

Vì vậy, nếu đầu vào là [113, 215, 221], thì đầu ra sẽ là 12, Cây mà danh sách đại diện là

Tổng đường dẫn là (3 + 5) + (3 + 1) =12.

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

• Xác định một biểu đồ bản đồ

• Xác định một hàm dfs (), hàm này sẽ lấy nút, cấp, vị trí, tổng khởi tạo nó bằng 0,

• isLeaf:=true

• để khởi tạo i:=0, khi i

  • Xác định một cặp tạm thời:=graph [level + 1, i]

  • nếu temp.first / 2 giống với pos, thì -

    • isLeaf:=false

    • dfs (temp.second, level + 1, temp.first, sum + node)

• nếu isLeaf khác 0, thì -

  • ret:=ret + (sum + nút)

• Từ phương thức chính, hãy làm như sau,

• ret:=0

• để khởi tạo i:=0, khi tôi

  • x:=nums [i]

  • val:=x mod 10

  • x:=x / 10

  • pos:=x mod 10

  • x:=x / 10

  • cấp:=x

  • chèn {(shift 1 bên trái (mức - 1) lần), val} vào cuối biểu đồ [mức]

• dfs (graph [1, 0] .second, 1, graph [1, 0] .first)

• trả lại ret

Ví dụ

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int ret;
   map <int, vector < pair <int, int> > > graph;
   void dfs(int node, int level, int pos, int sum = 0){
      bool isLeaf = true;
      for (int i = 0; i < graph[level + 1].size(); i++) {
         pair<int, int> temp = graph[level + 1][i];
         if (temp.first / 2 == pos) {
            isLeaf = false;
            dfs(temp.second, level + 1, temp.first, sum + node);
         }
      }
      if (isLeaf) {
         ret += (sum + node);
      }
   }
   int pathSum(vector<int>& nums) {
      ret = 0;
      for (int i = 0; i < nums.size(); i++) {
         int x = nums[i];
         int val = x % 10;
         x /= 10;
         int pos = x % 10;
         x /= 10;
         int level = x;
         graph[level].push_back({ (1 << (level - 1)) + pos - 1, val });
      }
      dfs(graph[1][0].second, 1, graph[1][0].first);
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {113,215,221};
   cout<<(ob.pathSum(v));
}

Đầu vào

{113,215,221}

Đầu ra

12