6057. 统计值等于子树平均值的节点数

leetcode 6057. 统计值等于子树平均值的节点数

题目：6057. 统计值等于子树平均值的节点数

给你一棵二叉树的根节点 root ，找出并返回满足要求的节点数，要求节点的值等于其 子树 中值的 平均值 。

注意:

• n 个元素的平均值可以由 n 个元素 求和 然后再除以 n ，并 向下舍入 到最近的整数。

• root 的 子树 由 root 和它的所有后代组成。

示例1:

输入: root = [4,8,5,0,1,null,6]
输出: 5
解释:

• 对值为 4 的节点：子树的平均值 (4 + 8 + 5 + 0 + 1 + 6) / 6 = 24 / 6 = 4 。
• 对值为 5 的节点：子树的平均值 (5 + 6) / 2 = 11 / 2 = 5 。
• 对值为 0 的节点：子树的平均值 0 / 1 = 0 。
• 对值为 1 的节点：子树的平均值 1 / 1 = 1 。
• 对值为 6 的节点：子树的平均值 6 / 1 = 6 。

示例2:

输入: root = [1]
输出: 1

解释：

• 对值为 1 的节点：子树的平均值 1 / 1 = 1。

提示:

• 树中节点数目在范围 [1, 1000] 内
• 1 <= k <= 10
• s 由小写英文字母组成

方法：DFS（深度优先搜索）

思路：DFS（深度优先搜索），打破DFS递归只能返回void或int的固有观念，每次递归同时将子树的节点和sum、子树的节点总数count一起返回，统计节点的值等于其子树中值的平均值的节点数。

运行数据：执行用时：0 ms，内存消耗：41.1 MB

复杂度分析：

• 时间复杂度：O(n)，n为节点个数。
• 空间复杂度：O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

private int cnt = 0;

// LeetCode指定调用方法
public int averageOfSubtree(TreeNode root) {

    dfs(root);
    return cnt;
}

private int[] dfs(TreeNode root) {

    if (root == null) {
        return new int[]{0,0};
    }

    int[] l = dfs(root.left);
    int[] r = dfs(root.right);
    int sum =  root.val + l[0] + r[0];
    int count = 1 + l[1] + r[1];
    if (sum / count == root.val) {
        cnt++;
    }

    return new int[]{sum, count};
}

学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。

才疏学浅，若有错误或不当之处，可批评指正，还请见谅！