ACM - CF1490D - 递归

题目链接

题意：结合题目的图来看
给定一个数组{3，5，2，1，4}.以该数组的最大数值作为根节点，左右依次二分递归，建立一棵二叉树。问，最终，这个数组中所有节点在这棵二叉树的深度。
结合图示，答案为：1 0 2 3 1

思路：
数据很小，n=100.每次找最大值的过程，可以直接for循环找，数据不大。
那么，每次找到最大值之后，对左右两边都递归同样操作，深度增加即可。
dfs标准姿势。
边界数据就是到了单个叶子节点。

代码：

#include <bits/stdc++.h>
using namespace std;

const int maxn = 150;

int T;
int a[maxn];
int ans[maxn];
int n;

void dfs(int step, int l, int r){
    if (l == r){
        ans[l] = step;
        return;
    }
    int pos, maxnum = -1;
    for(int i = l; i <= r; i++)
        if (maxnum < a[i])
            maxnum = a[i], pos = i;
    ans[pos] = step;
    if (pos > l) dfs(step + 1, l, pos - 1);
    if (pos < r) dfs(step + 1, pos + 1, r);
    return;
}

int main(){
    //freopen("input.txt", "r", stdin);
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]), ans[i] = 0;
        dfs(0, 1, n);
        for(int i = 1; i <= n; i++)
            printf("%d%c", ans[i], i == n ? '\n' : ' ');
    }
    return 0;
}