当前位置：首页 > news >正文

Leetcode—515.在每个树行中找最大值【中等】

news 2025/9/11 18:18:49

2023每日刷题（二十三）

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

在这里插入图片描述

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 10003void 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; 
}