C语言递归之在每个树行中找最大值

题目描述

您需要在二叉树的每一行中找到最大的值。

示例

输入:

          1
         / \
        3   2
       / \   \
      5   3   9

输出: [1, 3, 9]

题目要求

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     struct TreeNode *left;
 6  *     struct TreeNode *right;
 7  * };
 8  */
 9
10
11 /**
12  * Note: The returned array must be malloced, assume caller calls free().
13  */
14 int* largestValues(struct TreeNode* root, int* returnSize){
15
16 }

题解

 1 int max(int a,int b){
 2     return a>b?a:b;
 3 }
 4
 5 int work(struct TreeNode* r, int* ar, int f){
 6     ar[f]=max(ar[f],r->val);
 7     if(r->left==NULL&&r->right==NULL)return f+1;
 8     else if(r->left==NULL)return work(r->right,ar,f+1);
 9     else if(r->right==NULL)return work(r->left,ar,f+1);
10     else return max(work(r->left,ar,f+1),work(r->right,ar,f+1));
11 }
12
13 int* largestValues(struct TreeNode* root, int* returnSize){
14     int *array=(int *)malloc(5000*sizeof(int));
15     for(int i=0;i<5000;i++)array[i]=-2147483648;
16     if(root==NULL){
17         *returnSize=0;
18         return array;
19     }
20     *returnSize=work(root,array,0);
21     return array;
22 }

1.递归

这道题用BFS逻辑比较简单但是需要消耗大量内存去存储节点值，我最近在学习DFS，所以就用DFS实现。

这道题用DFS思路，切入点不太好想出来。

分析逻辑是每搜索到一个节点，就将其节点值与返回数组对应位置的值进行比较，若对应位置无值则直接插入，若对应位置有值则填入更大者，对应位置的下标即是节点的深度。

因此只要用深搜的思路遍历每一个节点，遍历携带参数为节点深度，就可以用时间复杂度为O(n)解决此问题。

2.非指针变量的值

这道题一开始我遇到了一些困惑