資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的路徑總和 IV
假設我們有一個整數列表，它表示一個深度小於 5 的二叉樹。如果樹的深度小於 5，則該樹可以用一個三位整數列表表示。對於此列表中的每個整數 -
百位數字表示該節點的深度 D，1 <= D <= 4。
十位數字表示該節點在其所屬級別的位置 P，範圍為 1 到 8。位置與完整二叉樹中的位置相同。
個位數字用於表示該節點的值 V，0 <= V <= 9。
我們必須找到從根到葉的所有路徑的總和。
因此，如果輸入類似於 [113, 215, 221]，則輸出將為 12，列表表示的樹為
路徑總和為 (3 + 5) + (3 + 1) = 12。
要解決此問題，我們將遵循以下步驟 -
定義一個對映圖
定義一個函式 dfs()，它將接收節點、級別、位置、總和，並將其初始化為 0，
isLeaf := true
對於初始化 i := 0，當 i < graph[level + 1] 的大小，更新（i 增加 1），執行 -
定義一個對 temp := graph[level + 1, i]
如果 temp.first / 2 與 pos 相同，則 -
isLeaf := false
dfs(temp.second, level + 1, temp.first, sum + node)
如果 isLeaf 不為零，則 -
ret := ret + (sum + node)
從主方法執行以下操作，
ret := 0
對於初始化 i := 0，當 i < nums 的大小，更新（i 增加 1），執行 -
x := nums[i]
val := x mod 10
x := x / 10
pos := x mod 10
x := x / 10
level := x
將 { (將 1 左移 (level - 1) 次)，val } 插入到 graph[level] 的末尾
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
237 次檢視
