Leetcode—剑指OfferII LCR 044.在每个树行中找最大值【中等】

2023每日刷题（二十三）

Leetcode—LCR 044.在每个树行中找最大值

在这里插入图片描述

DFS实现代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
#define MAX(a, b) ((a > b ? (a) : (b)))
#define MAXSIZE 10003

void dfs(int *res, int cur, int *pos, struct TreeNode* root) {
    if(*pos == cur) {
        res[(*pos)++] = root->val;
    } else {
        res[cur] = MAX(res[cur], root->val);
    }
    if(root->left) {
        dfs(res, cur + 1, pos, root->left);
    }
    if(root->right) {
        dfs(res, cur + 1, pos, root->right);
    }
}

int* largestValues(struct TreeNode* root, int* returnSize) {
    *returnSize = 0;
    if(root == NULL) {
        return NULL;
    }
    int *res = (int *)malloc(sizeof(int) * MAXSIZE);
    dfs(res, 0, returnSize, root);
    return res;
}

运行结果

在这里插入图片描述

BFS实现代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
#define MAXSIZE 10003
#define MAX(a, b) ((a > b) ? (a) : (b))

int* largestValues(struct TreeNode* root, int* returnSize){
    struct TreeNode **queue = (struct TreeNode **)malloc(sizeof(struct TreeNode*)*MAXSIZE);
    *returnSize = 0;
    int *res = (int *)malloc(sizeof(int)*MAXSIZE);
    if(root == NULL) {
        return NULL;
    }
    int pos = 0;
    int front = 0, rear = 0;
    int len = 0;
    queue[rear++] = root;
    while(front != rear) {
        len = rear - front;
        int maxVal = INT_MIN;
        while(len > 0) {
            len--;
            struct TreeNode *tmp = queue[front++];
            maxVal = MAX(maxVal, tmp->val);
            if(tmp->left) {
                queue[rear++] = tmp->left;
            }
            if(tmp->right) {
                queue[rear++] = tmp->right;
            }
        }
        res[pos++] = maxVal;
    }
    *returnSize = pos;
    free(queue);
    return res; 
}