LeetCode 解題筆記：2265. Count Nodes Equal to Average of Subtree

作者：王一哲
日期：2026年9月10日


LeetCode 題目連結：2265. Count Nodes Equal to Average of Subtree

解題想法

中等難度題，這題考二元樹及 dfs。題目給一棵二元樹的根節點 $root$，要找出有幾個節點本身及其子節點的平均值與節點的值相等，主要的解題過程在於如何設計一個遞迴函式，從代入的節點一路往下走，計算所有子節點的加總及數量，請看程式碼會比較清楚。

Python 程式碼

Runtime: 46 ms, beats 85.47%. Memory: 19.64 MB, beats 33.89%.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def averageOfSubtree(self, root: TreeNode) -> int:
        ans = 0

        def dfs(node):
            # ans 要設定成非區域變數，才能在函式中修改數值
            nonlocal ans
            
            # 遞迴出口，沒有節點，回傳 (加總, 數量) (0, 0)
            if not node: return (0, 0)
            
            # 遞迴，代入左子樹、右子樹，求各自的加總及子節點數量
            lsum, lcnt = dfs(node.left)
            rsum, rcnt = dfs(node.right)
            # 合併，左、右子數的加總及數量，加上這個節點的值及數量 1
            total = lsum + node.val + rsum
            cnt = lcnt + 1 + rcnt
            # 如果這個節點以下的平均等於這個節點的值，答案加 1
            if total // cnt == node.val:
                ans += 1
            # 回傳這個節點的加總及節點數量
            return (total, cnt)
        # 呼叫 dfs，代入根節點找答案，最後回傳答案
        dfs(root)
        return ans

C++ 程式碼

Runtime: 7 ms, beats 54.96%. Memory: 15.76 MB, beats 64.72%.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int ans;  // 設定成非區域變數，才能在函式中修改數值

    pair<int, int> dfs(TreeNode* node) {
        // 遞迴出口，沒有節點，回傳 (加總, 數量) (0, 0)
        if (node == nullptr) return {0, 0};
        
        // 遞迴，代入左子樹、右子樹，求各自的加總及子節點數量
        auto left_val = dfs(node->left);
        int lsum = left_val.first, lcnt = left_val.second;
        auto right_val = dfs(node->right);
        int rsum = right_val.first, rcnt = right_val.second;
        // 合併，左、右子數的加總及數量，加上這個節點的值及數量 1
        int total = lsum + node->val + rsum;
        int cnt = lcnt + 1 + rcnt;
        // 如果這個節點以下的平均等於這個節點的值，答案加 1
        if (total / cnt == node->val) ans++;
        // 回傳這個節點的加總及節點數量
        return {total, cnt};
    }

    int averageOfSubtree(TreeNode* root) {
        // 呼叫 dfs，代入根節點找答案，最後回傳答案
        ans = 0;  // 先歸零
        dfs(root);
        return ans;
    }
};