久違的 Leetcode Daily,今天剛好在參考其它人的解答時想到一些有趣的議題可以分享。
關於題目的分析與解答我就不另外贅述,因為今天要討論的這篇參考解答已經寫得非常精采。
參考解答分析
在參考解答中,vanAmsen 給出了一共 8 種程式語言的解法,儘管思路上大同小異但卻不失為一個很好的參考。
以下就用它的 C++ 版本作為範例:
class Solution {
public:
int averageOfSubtree(TreeNode* root) {
int result = 0;
traverse(root, result);
return result;
}
private:
pair<int, int> traverse(TreeNode* node, int& result) {
if (!node) return {0, 0};
auto [left_sum, left_count] = traverse(node->left, result);
auto [right_sum, right_count] = traverse(node->right, result);
int curr_sum = node->val + left_sum + right_sum;
int curr_count = 1 + left_count + right_count;
if (curr_sum / curr_count == node->val) result++;
return {curr_sum, curr_count};
}
};
得益於 C++ 的 STL pair 容器 與 C++ 17 的 Structured Binding 特性,使得 C++ 可以一次性回傳多個值。
許多現代化的程式語言(例如 Go 或 Python)都允許函式回傳多個值,這很大程度上幫助工程師專注於邏輯。
以 C 實作
我是一個比較傳統的人,像這種題目我一般會偏好用 C 作答。此時便衍生出一個問題:應該如何使 C 回傳多個值?
結構體
眾所周知,用結構體就可以把多個變數包起來,可以藉由定義一個結構體 Pair
來達成這個目標:
typedef struct Pair {
int sum;
int cnt;
} P;
P traverse(struct TreeNode *n, int *max) {
if (!n) return (P){0, 0};
P left = traverse(n->left, max);
P right = traverse(n->right, max);
int curr_sum = n->val + left.sum + right.sum;
int curr_cnt = 1 + left.cnt + right.cnt;
if (curr_sum / curr_cnt == n->val) (*max)++;
return (P){curr_sum, curr_cnt};
}
int averageOfSubtree(struct TreeNode *root){
int ans = 0;
traverse(root, &ans);
return ans;
}