C++でのパス合計IV

深さが5未満の二分木を表す整数のリストがあるとします。木の深さが5未満の場合、このツリーは3桁の整数のリストで表すことができます。このリストの整数ごとに-

• 百の位は、このノードの深さD、1 <=D<=4を表します。

• 十の位は、1から8の範囲に属するレベルでのこのノードの位置Pを表します。位置は完全な二分木の位置と同じです。

• 単位の桁は、このノードの値V、0 <=V<=9を表すために使用されます。

根から葉に向かうすべての経路の合計を見つける必要があります。

したがって、入力が[113、215、221]の場合、出力は12になります。リストが表すツリーは

パスの合計は（3 + 5）+（3 + 1）=12です。

これを解決するには、次の手順に従います-

• 1つのマップグラフを定義する

• 関数dfs（）を定義します。これにより、ノード、レベル、位置が取得され、合計で0で初期化されます。

• isLeaf：=true

• 初期化i：=0の場合、i<グラフのサイズ[レベル+1]の場合、更新（iを1増やします）、実行-

  • 1つのペアを定義しますtemp：=graph [level + 1、i]

  • temp.first / 2がposと同じ場合、-

    • isLeaf：=false

    • dfs（temp.second、level + 1、temp.first、sum + node）

• isLeafがゼロ以外の場合、-

  • ret：=ret +（合計+ノード）

• メインの方法から、次のようにします。

• ret：=0

• 初期化i：=0の場合、i

  • x：=nums [i]

  • val：=x mod 10

  • x：=x / 10

  • pos：=x mod 10

  • x：=x / 10

  • レベル：=x

  • グラフの最後に{（左に1シフト（レベル-1）回）、val}を挿入します[レベル]

• dfs（graph [1、0] .second、1、graph [1、0] .first）

• retを返す

例

理解を深めるために、次の実装を見てみましょう-

#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));
}

入力

{113,215,221}

出力

12