题目

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

示例

思路

**深度优先**

我们定义一个数组，然后遍历树节点，遍历过程中我们将同一高度的节点进行比较，用数组保存同一高度的最大值

数组初始化的时候，可以将数组元素复都最小值，但是那样太麻烦了，所以当我们第一次遍历到新的高度时，先保存当前元素的值，当下次再遍历到相同高度我们再做比较

**广度优先**

我们对树进行层次遍历，一层一层输出，每次输出之前保存本层最大值即可

代码

深度优先

/**
* 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_NODE_SIZE 10001
#define MAX(a, b) ((a) > (b) ? (a) : (b))

void dfs(int *res, int *pos, struct TreeNode* root, int curHeight) {
    if (curHeight == *pos) {//先对数组进行初始化，保存到最深高度的树，也可以将数组元素复最小值，但是那样太麻烦了
        res[(*pos)++] = root->val;
    } else {
        res[curHeight] = MAX(res[curHeight], root->val);//比较同层高度的值
    }
    if (root->left) {//当前比较完了，下一层
        dfs(res, pos, root->left, curHeight + 1);
    }
    if (root->right) {//当前比较完了，下一层
        dfs(res, pos, root->right, curHeight + 1);
    }
} 
/*
*int* largestValues：树中同一高度的最大值
struct TreeNode* root：树的头结点
int* returnSize:返回值数组的长度
返回值：返回树中同一高度的最大值，并保存在数组中
*/
int* largestValues(struct TreeNode* root, int* returnSize) {
    if (!root) {
        *returnSize = 0;
        return NULL;
    }
    int *res = (int *)malloc(sizeof(int) * MAX_NODE_SIZE);
    *returnSize = 0;
    dfs(res, returnSize, root, 0);
    return res;
}

广度优先 

/**
 * 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)
/*
*int* largestValues：树中同一高度的最大值
struct TreeNode* root：树的头结点
int* returnSize:返回值数组的长度
返回值：返回树中同一高度的最大值，并保存在数组中
*/

int* largestValues(struct TreeNode* root, int* returnSize){
    struct TreeNode * queue[10001];//定义队列
    int head = 0, tail = 0;//队列指针
    int * ans = malloc(sizeof(int) * 10001);
    *returnSize = 0;
    if(root == NULL)
    {
        return NULL;
    }
    int i;
    queue[head++] = root;//头结点入队
    while(tail < head)//层次遍历树，每遍历一次，保存一个最大值
    {
        i = head;//当前层有多少个元素，i-tail
        ans[(*returnSize)] = queue[tail]->val;//先初始化当前层的数组
        while(tail < i)
        {
            ans[(*returnSize)] = MAX(ans[(*returnSize)] , queue[tail]->val);//每次保存最大值
            if(queue[tail]->left)//左节点存在入队
            {
                queue[head++] = queue[tail]->left;
            }
            if(queue[tail]->right)//右节点存在入队
            {
                queue[head++] = queue[tail]->right;
            }
            tail++;
        }
        (*returnSize)++;
    }
    return ans;
}

时间空间复杂度