题目
思路:
dfs树的每一条到叶子的路径, 并计算路径中需要修改的个数, 在这些个数中取最小值文章来源：https://www.toymoban.com/news/detail-793313.html
注意:
本题中的树是以每个结点的左右孩子是什么的形式给出的, 所以可以不用建树, 只需保存每个结点的左右孩子是什么即可。文章来源地址https://www.toymoban.com/news/detail-793313.html
代码：
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<PII, int> PIII;
const int inf = 0x3f3f3f3f;
const ll infinf = 0x3f3f3f3f3f3f3f3f;
const int N = 3e5 + 10;
int l[N], r[N];
int n;
string s;
void dfs(int i, int cnt, int &res) {
if (l[i] == 0 && r[i] == 0) res = min(res, cnt);
if (l[i] != 0) {
if (s[i - 1] != 'L') dfs(l[i], cnt + 1, res);
else dfs(l[i], cnt, res);
}
if (r[i] != 0) {
if (s[i - 1] != 'R') dfs(r[i], cnt + 1, res);
else dfs(r[i], cnt, res);
}
}
void solve() {
cin >> n;
cin >> s;
for (int i = 1; i <= n; i ++) cin >> l[i] >> r[i];
int ans = inf;
dfs(1, 0, ans);
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t; cin >> t;
while (t --) solve();
return 0;
}
到了这里，关于Codeforces Round 911 (Div. 2) C. Anji‘s Binary Tree (DFS + 树)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
