C++의 경로 합 IV

<시간/>

깊이가 5보다 작은 이진 트리를 나타내는 정수 목록이 있다고 가정합니다. 트리의 깊이가 5보다 작으면 이 트리는 세 자리 정수 목록으로 나타낼 수 있습니다. 이 목록의 각 정수에 대해 -

100자리는 이 노드의 깊이 D, 1 <=D <=4를 나타냅니다.
10자리는 1에서 8까지의 범위에 속하는 레벨에서 이 노드의 위치 P를 나타냅니다. 위치는 전체 이진 트리의 위치와 동일합니다.
단위 자릿수는 이 노드의 값 V를 나타내는 데 사용됩니다. 0 <=V <=9.

루트에서 잎으로 가는 모든 경로의 합을 찾아야 합니다.

따라서 입력이 [113, 215, 221]과 같으면 출력은 12가 됩니다. 목록이 나타내는 트리는 다음과 같습니다.

C++의 경로 합 IV

경로 합계는 (3 + 5) + (3 + 1) =12입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

하나의 지도 그래프 정의
dfs() 함수를 정의하면 노드, 레벨, 위치, 합계가 0으로 초기화됩니다.
isLeaf :=참
for initialize i :=0, i
- 한 쌍의 온도 정의 :=그래프[레벨 + 1, i]
- temp.first / 2가 pos와 같으면 -
  - isLeaf :=거짓
  - dfs(temp.second, 레벨 + 1, temp.first, 합계 + 노드)
isLeaf가 0이 아니면 -
- ret :=ret + (합 + 노드)
기본 방법에서 다음을 수행합니다.
ret :=0
initialize i :=0의 경우, i <숫자의 크기일 때 업데이트(i를 1만큼 증가), 수행 -
- x :=숫자[i]
- val :=x 모드 10
- x :=x / 10
- 위치 :=x 모드 10
- x :=x / 10
- 레벨 :=x
- 그래프[레벨]의 끝에 { (왼쪽으로 1 이동(레벨 - 1)번 이동), val } 삽입
dfs(그래프[1, 0].초, 1, 그래프[1, 0].첫 번째)
리턴 렛

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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