Leetcode每日一题 —— 2265. 统计值等于子树平均值的节点数

dfs,pair维护数目和值。

/**

 * 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 averageOfSubtree(TreeNode* root) {

        int res = 0;

        auto solve = [&](this auto&& solve, TreeNode* p) -> pair<int,int> {

            if(p == nullptr) {

                return make_pair(0,0);

            }

            auto lson = solve(p->left);

            auto rson = solve(p->right);

            auto f = make_pair(lson.first + rson.first + p->val, lson.second + rson.second + 1);

            if(f.first / f.second == p->val) {

                res++;

            }

            return f;

        };

        solve(root);

        return res;

    }

};

典型的后续遍历，维护节点数量和节点总和两个状态。

class Solution {

public:

    int averageOfSubtree(TreeNode* root) {

        // 典型的后序遍历，同时维护节点数量和节点总和

        int res=0;

        auto postorder=[&](auto&& self,TreeNode* node) -> pair<int,int> {

            if(node==nullptr){

                return make_pair(0,0);

            }

            int sum=0;

            int cnt=0;

            auto left=self(self,node->left);

            auto right=self(self,node->right);

            cnt+=left.first+right.first+1;

            sum+=left.second+right.second+node->val;

            if(sum/cnt==node->val){

                res++;

            }

            return make_pair(cnt,sum);

        };

        postorder(postorder,root);

        return res;

    }

};

很经典的树形遍历题，维护节点值和，节点数量以及符合要求的节点数量三个值

public class Solution {

    public int AverageOfSubtree(TreeNode root)

    {

        return Collect(root).matches;

    }

    

    //第一个为和，第二个为节点数量，当前子树内内满足条件的节点数量

    private (int sum, int count, int matches) Collect(TreeNode root)

    {

        if (root == null) return (0, 0, 0);

        var left = Collect(root.left);

        var right = Collect(root.right);

        int sum = left.sum + right.sum + root.val;

        int numberNodes = left.count + right.count + 1;

        int mean = sum / numberNodes;

        int satisfiedNumber = left.matches + right.matches + (mean == root.val ? 1 : 0);

        

        return (sum, numberNodes, satisfiedNumber);

    }

}

简单的dfs

算术评级 4 第 292 场周赛 Q2 难度分 1473

class Solution:

    def averageOfSubtree(self, root: TreeNode) -> int:

        def dfs(node):

            if not node:

                return 0,0,0

            left_ans, left_sum, left_num = dfs(node.left)

            right_ans, right_sum, right_num = dfs(node.right)

            all_sum=node.val+left_sum+right_sum

            all_num=left_num+right_num+1

            if node.val==all_sum//all_num:

                ans=1

            else:

                ans=0

            return ans+left_ans+right_ans, all_sum, all_num

        return dfs(root)[0]

Kotlin每日打卡（二叉树dfs）：

/**

 * Example:

 * var ti = TreeNode(5)

 * var v = ti.`val`

 * Definition for a binary tree node.

 * class TreeNode(var `val`: Int) {

 *     var left: TreeNode? = null

 *     var right: TreeNode? = null

 * }

 */

class Solution {

    fun averageOfSubtree(root: TreeNode?): Int {

        var ans = 0

        fun dfs(root: TreeNode?): IntArray {

            if (root == null) {

                return intArrayOf(0, 0)

            }

            val (leftCount, leftSum) = dfs(root.left)

            val (rightCount, rightSum) = dfs(root.right)

            val count = leftCount + rightCount + 1

            val sum = leftSum + rightSum + root.`val`

            if (sum / count == root.`val`) {

                ans++

            }

            return intArrayOf(count, sum)

        }

        dfs(root)

        return ans

    }

}