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

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

运行结果

之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！