CSP - J day8

一. 二叉树

 

 （1）思路

· 因为是二叉树，一个节点最多只有两个子节点，不需要用vector建树，仅用结构体就可以完成。

· 碰到 ' U ' 必改， 碰到 ' L ' 分两路：不改，就按 ' L ' 走；改成 ' R '，变成向右走，次数加一。

（2）代码

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5, INF = 0x3f3f3f3f;struct node
{int l, r;	
}a[N];int n, ans;
string s;void dfs(int x, int cnt)
{if (a[x].l == 0 && a[x].r == 0)ans = min(ans, cnt);if (a[x].l != 0){if (s[x - 1] == 'L')dfs(a[x].l, cnt);elsedfs(a[x].l, cnt + 1);}if (a[x].r != 0){if (s[x - 1] == 'R')dfs(a[x].r, cnt);elsedfs(a[x].r, cnt + 1);}
}int main()
{cin >> n >> s;for (int i = 1; i <= n; i ++){cin >> a[i].l >> a[i].r; }ans = INF;dfs(1, 0);cout << ans;return 0;
}