【题目】求二叉树的最大深度

有一个二叉树 root ，它的每个节点都有一个值，它的深度为从根到该节点的路径长度（根的深度为 1）。
给定一个整型列表 target，target[i]对应的[最大深度]定义为：
若二叉树中存在节点值大于 target[i] 的节点，则这些节点中最大的深度为 target[i] 的[最大深度];
若二叉树中不存在节点值大于 target[i] 的节点，则 target[i] 的[最大深度]为 -1。
请计算 target 中每个元素的「最大深度」，并按 target 下标顺序依次存入序列返回。

例1：
输入：
target = [2,7]
root = [5,3,7,1,5]
输出：
[3,-1]

解析：
首先确定每个节点的深度，
target[0] = 2：节点值大于 2 的节点有root[0]、root[1]、root[2]、root[4]，其中root[4]深度最大（为 3），所以其「最大深度」为 3；
target[1] = 7：没有大于 7 的节点，所以其「最大深度」为 -1；
最后返回 [3,-1]。

例2：
输入：
target = [6,2,9,7,9]
root = [3,4,11,3,null,null,8,7,null,5]
输出：
[4,4,2,3,2]

解析：
target[0] = 6：节点值大于 6 的节点有root[2]、root[6]、root[7]，其中root[7]深度最大（为 4），所以其「最大深度」为 4；
target[1] = 2：所有非空节点的值都大于2，所以其「最大深度」为 4；
target[2] = 9：大于 9 的节点只有root[2]，所以其「最大深度」为 2；
target[3] = 7：大于 7 的节点有root[2]、root[6]，所以其「最大深度」为 3；
target[4] = 9：大于 9 的节点只有root[2]，所以其「最大深度」为 2；
最后返回 [4,4,2,3,2]。

提示：
1 <= target.length <= 10^5
1 <= target[i] <= 10^5
1 <= 节点总数 <= 50000 且 1 <= 节点值 <= 10^5

思路：
1.dfs方式遍历整棵树，得到每个节点值的最大深度。
2.dfs过程中，用个大数组record记录每个节点的最大深度。
3.注意：不同节点的节点值可能重复，例如示例1有两个节点的值为5，所以此时要更新深度值。
4.更新record数组，方法是记录每个节点的后续最大深度。
5.最后，遍历target数组，对于每个target[i] 找出比target[i]大的有哪些节点。

主要代码段：

// 二叉树的结构
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

#define MAX 100001

void Dfs(struct TreeNode *node, int depth, int *record)
{
    if (node == NULL) {
        return;
    }

    record[node->val] = fmax(depth, record[node->val]);
    Dfs(node->left, depth + 1, record);
    Dfs(node->right, depth + 1, record);
    return;
}

int *CalcuTreeNodeDeep(int *target, int targetSize, struct TreeNode *root, int *returnSize)
{
    int record[MAX] = { 0 };
    Dfs(root, 1, record);

    // 更新record数组,是其记录的是当前下标i对应的后续最大深度值
    int tempMax = record[MAX - 1]; // 记录当前最大深度值
    for (int i = MAX - 2; i >= 0; i--) {
        record[i] = fmax(tempMax, record[i]);
        tempMax = record[i];
    }

    // 记录返回结果
    int *res = calloc(targetSize, sizeof(int));
    for (int i = 0; i < targetSize; i++) {
        if (record[target[i] + 1] == 0) {
            res[i] = -1;
        } else {
            res[i] = record[target[i] + 1];
        }
    }

    *returnSize = targetSize;
    return res;
}

yo peace!