数据结构
网络
关系型数据库管理系统
操作系统
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 次查看
