LeetCode6057:计算与子树平均值相等的节点数量——深度优先搜索

给定一个二叉树的根节点 root，请找出并返回那些节点的值等于其子树中所有节点值的平均值的节点数量。

注意事项：

• 对于 n 个元素，它们的平均值可以通过将这 n 个元素的总和除以 n 得出，且结果应向下取整至最接近的整数。
• 一个节点的子树包含该节点及其所有的后代节点。

示例 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。

使用 DFS 进行二叉树的后序遍历

采用递归方式执行二叉树的后序遍历，可以有效地计算每个节点子树的总和及节点数，进而判断该节点是否符合题目条件。此方法中，我们通过一个数组来记录每个节点的子树节点总数、子树节点值总和以及满足条件的节点数。递归函数会从叶子节点开始向上返回这些信息，直至根节点，最终得出答案。

/**
* 二叉树节点定义
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
public int averageOfSubtree(TreeNode root) {
return dfs(root)[2];
}
private int[] dfs(TreeNode node) {
if (node == null) return new int[]{0, 0, 0}; // 基本情况：空节点
int[] leftResult = dfs(node.left);
int[] rightResult = dfs(node.right);
int totalSum = leftResult[0] + rightResult[0] + node.val;
int totalCount = leftResult[1] + rightResult[1] + 1;
int matchingNodes = leftResult[2] + rightResult[2];
if (node.val == totalSum / totalCount) {
return new int[]{totalSum, totalCount, matchingNodes + 1};
} else {
return new int[]{totalSum, totalCount, matchingNodes};
}
}
}