dfs|bfs建图

lc1001

discussion发现的圣经

反复诵读TvT

"每个变量、每个逻辑分支对内完成的是什么功能、对外在整体程序中扮演的角色是什么"

"对待游戏一样享受这个过程"

lc2385

dfs不建图

利用负数，一次遍历

class Solution {
int ans = 0, start;

int dfs(TreeNode* node) {
if (node == nullptr) {
return 0;
}
int l_len = dfs(node->left);
int r_len = dfs(node->right);
if (node->val == start) {
// 计算子树 start 的最大深度
ans = -min(l_len, r_len); // 负负得正
return 1; // 用正数表示找到了 start
}
if (l_len > 0 || r_len > 0) {
// 只有在左子树或右子树包含 start 时，才能更新答案
ans = max(ans, abs(l_len) + abs(r_len)); // 两条链拼成直径
return max(l_len, r_len) + 1; // max 会自动取到正数
}
return min(l_len, r_len) - 1; // 用负数表示没有找到 start
}

public:
int amountOfTime(TreeNode* root, int start) {
this->start = start;
dfs(root);
return ans;
}
};

bfs建图

一次bfs建表

一次bfs找最远层数

class Solution {
public:
int amountOfTime(TreeNode* root, int start) {
unordered_map<TreeNode*, TreeNode*> p;
TreeNode* s = nullptr;
queue<TreeNode*> q;
q.push(root);
p[root] = nullptr;
while (!q.empty()) {
auto t = q.front();
q.pop();
if (t->val == start) s = t;
if (t->left) {
p[t->left] = t;
q.push(t->left);
}
if (t->right) {
p[t->right] = t;
q.push(t->right);
}
}

unordered_map<TreeNode*, bool> v;
q.push(s);
v[s] = true;
int res = -1;
while (!q.empty()) {
int sz = q.size();
res++;
while (sz--) {
auto t = q.front();
q.pop();
if (t->left && !v[t->left]) {
v[t->left] = true;
q.push(t->left);
}
if (t->right && !v[t->right]) {
v[t->right] = true;
q.push(t->right);
}
if (p[t] && !v[p[t]]) {
v[p[t]] = true;
q.push(p[t]);
}
}
}
return res;
}
};

dfs建图+bfs

class Solution {
public:
int amountOfTime(TreeNode* root, int start) {
unordered_map<int, vector<int>> g;
function<void(TreeNode*)> dfs = [&] (TreeNode *root) {
if (root == nullptr || root->left == root->right)
return;


if (root->left) {
int u = root->val, v = root->left->val;
g[u].emplace_back(v);
g[v].emplace_back(u);
}

if (root->right) {
int u = root->val, v = root->right->val;
g[u].emplace_back(v);
g[v].emplace_back(u);
}

dfs(root->left);
dfs(root->right);
};
dfs(root);

int time = -1;
queue<int> q;
q.push(start);
unordered_set<int> visited{start};
while (!q.empty()) {
time++;
int len = q.size();
while (len--) {
int cur = q.front();
q.pop();
for (int nei : g[cur]) {
if (visited.find(nei) != visited.end()) {
continue;
}
q.push(nei);
visited.insert(nei);
}
}
}
return time;
}
};