題目描述
您需要在二叉樹的每一行中找到最大的值，
示例
輸入: 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.非指標變數的值
這道題一開始我遇到了一些困惑??
然后我就懷疑是不是 return max(work(r->left,ar,f+1),work(r->right,ar,f+1)) 的兩個函式并行執行了導致資料訪問和修改問題，
C語言是嚴格按順序執行的，不用去質疑異步執行、同步執行的問題，
最后刪去了第五行和第六行之間的 if(ar[f]==NULL){ar[f]=r->val;} 才解決，通過輸出中間結果我才了解到，0被當作NULL了，
3.陣列初始化
陣列的初始化不只是為其申請記憶體空間 int *array=(int *)malloc(5000*sizeof(int))
更要為其賦初值， for(int i=0;i<5000;i++)array[i]=-2147483648
或者使用 #include<string.h> 的memset函式 memset(array, 0, 5000)
memset的用法： # include <string.h> void *memset(void *s, int c, unsigned long n);
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/138805.html
標籤：其他