题目链接：666.路径和IV
解法：
参考这篇题解：【LeetCode - 666】路径和 IV_力扣666路径总和4-CSDN博客
关键点在于：
（1）使用map来存node：key 为整数的前两位，value 为整数的后一位，即 key 为位置信息，value 为权值，KV是(num / 10, num % 10);
（2）左右子树的表示：对于某一个节点来说，如果它的深度为depth，位置编号为 pos，那么它的左子节点的深度为depth+1，位置编号为 pos?× 2 - 1，那么key就是 (depth+1) * 10 + pos*2-1。而它的右子节点的pos和key都是左子节点的加1；
（3）如果左子节点和右子节点均不在 map 中，说明一条路径计算完毕，ans += sum；
（4）如果两个子节点中有一个不在map中，那么dfs会直接对该子节点return，否则继续dfs。
边界条件：左子树或者右子树为空。
时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
int ans = 0;
// 使用unordered_map，插入、删除和查找的平均时间复杂度为O(1)
// 而map是有序的，这三种操作为O(logn)
unordered_map<int,int> map;
public:
int pathSum(vector<int>& nums) {
for (int num: nums) {
map[num / 10] = num % 10;
}
dfs(nums[0]/10, 0);
return ans;
}
private:
void dfs(int node, int sum) {
auto it = map.find(node);
if (it == map.end()) {
return;
}
sum += it->second;
int depth = node / 10;
int pos = node % 10;
int left = (depth + 1) * 10 + pos * 2 - 1;
int right = left + 1;
if (map.find(left)==map.end() && map.find(right)==map.end()) {
ans += sum;
} else {
dfs(left, sum);
dfs(right, sum);
}
}
};题目链接：207.course-schedule
解法：
两种解法，bfs和dfs。
bfs：需要提前计算所有课的入度和先修课的邻接表，入度为0的课意味着没有任何先修课，可以先选。剩下的看题解，这篇题解写得很好：bfs题解。
代码的实现参考这篇题解：bfs代码
dfs：在构造邻接表时，有的答案是把先修课作为vector的索引或者map的key，也有的把先修课作为vector的元素。这里按前一种，把先修课作为vector的索引，得从先修课开始选，根据先修课再去遍历以它为前置条件的课程，直到搜索到某门课不是任何课程的先修课，说明从当前课开始dfs的路径，是有限无环的。
以下题解来自eetcode中文区：dfs代码
边界条件：
时间复杂度 O(N+M)： 遍历一个图需要访问所有节点和所有临边，N?和 M分别为节点数量和临边数量；
空间复杂度 O(N+M)： 为建立邻接表所需额外空间，adjacency 长度为 N?，并存储 M条临边的数据。
// bfs
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> adjacency(numCourses);
vector<int> indegrees(numCourses, 0);
queue<int> que;
for (const auto& cp:prerequisites) {
adjacency[cp[1]].push_back(cp[0]);
indegrees[cp[0]]++;
}
for (int i=0; i<numCourses; i++) {
if (indegrees[i]==0) que.push(i);
}
while (!que.empty()) {
int pre = que.front();
que.pop();
numCourses--;
for (int cur: adjacency[pre]) {
indegrees[cur]--;
if (indegrees[cur]==0) que.push(cur);
}
}
return numCourses == 0;
}
};// dfs
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> adjacency(numCourses);
vector<int> flags(numCourses, 0);
for (const auto& cp:prerequisites) {
adjacency[cp[1]].push_back(cp[0]);
}
for (int i=0; i<numCourses; i++) {
if (!dfs(adjacency, flags, i)) return false;
}
return true;
}
private:
bool dfs(const vector<vector<int>>& adjacency, vector<int>& flags, int i) {
if (flags[i] == 1) return false;
if (flags[i] == -1) return true;
flags[i] = 1;
for (int j: adjacency[i]) {
if (!dfs(adjacency, flags, j)) return false;
}
flags[i] = -1;
return true;
}
};解法：
与207几乎一样，代码改动量很小。如果不先做207，那几乎是搞不懂的。
dfs改动大一些，result需要翻转一下，因为先修课是最后才加入列表的。
边界条件：
时间复杂度：同207
空间复杂度：同207
// bfs
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> adjacency(numCourses);
vector<int> indegrees(numCourses, 0);
queue<int> que;
vector<int> result;
for (const auto& cp:prerequisites) {
adjacency[cp[1]].push_back(cp[0]);
indegrees[cp[0]]++;
}
for (int i=0; i<numCourses; i++) {
if (indegrees[i]==0) que.push(i);
}
while (!que.empty()) {
int pre = que.front();
que.pop();
result.push_back(pre);
for (int cur: adjacency[pre]) {
indegrees[cur]--;
if (indegrees[cur]==0) que.push(cur);
}
}
if (result.size()!=numCourses) return {};
return result;
}
};// dfs
class Solution {
vector<int> result;
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> adjacency(numCourses);
vector<int> flags(numCourses, 0);
for (const auto& cp:prerequisites) {
adjacency[cp[1]].push_back(cp[0]);
}
for (int i=0; i<numCourses; i++) {
if (!dfs(adjacency, flags, i)) return {};
}
// 要翻转
reverse(result.begin(), result.end());
return result;
}
private:
bool dfs(const vector<vector<int>>& adjacency, vector<int>& flags, int i) {
if (flags[i] == 1) return false;
if (flags[i] == -1) return true;
flags[i] = 1;
for (int j: adjacency[i]) {
if (!dfs(adjacency, flags, j)) return false;
}
flags[i] = -1;
result.push_back(i);
return true;
}
};