剑指 Offer II 044. 二叉树每层的最大值-dfs法

剑指 Offer II 044. 二叉树每层的最大值

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

示例1：

输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
解释:
1
/
3 2
/ \ \
5 3 9

示例2：

输入: root = [1,2,3]
输出: [1,3]
解释:
1
/
2 3

示例3：

输入: root = [1]
输出: [1]

示例4：

输入: root = [1,null,2]
输出: [1,2]
解释:
1

2

示例5：

输入: 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(). */
 int f(struct TreeNode* root){
    
     if(root){
    
         int a=f(root->left)+1;
         int b=f(root->right)+1;
         if(a>b){
    
             return a;
         }
         else{
    
             return b;
         }
     }
     else{
    
         return 0;
     }
 }

  void f2(struct TreeNode* root,int h,int *a){
    
     if(root){
    
         f2(root->left,h+1,a);
        f2(root->right,h+1,a);
         if(root->val>a[h]){
    
             a[h]=root->val;
         }
      
     }
     
 }
int* largestValues(struct TreeNode* root, int* returnSize){
    
    int  h=f(root);
    int *re=(int *)malloc(sizeof(int)*h);
    * returnSize=h;
    for(int i=0;i<h;i++){
    
        re[i]=-2147483648;
    }
   f2(root,0,re);
   return re;

}