一、题目分析
题目要求统计二叉树中满足 “节点值等于其所在子树平均值” 的节点数量。子树平均值的计算规则为：子树所有节点值之和 ÷ 子树节点总数。
示例解析
以输入root = [4,8,5,0,1,null,6]为例：
- 节点 4 的子树包含 6 个节点，总和为 24，平均值为 4，与节点值相等，符合条件。
- 节点 5 的子树包含 2 个节点，总和为 11，平均值为 5，与节点值相等，符合条件。
- 叶子节点 0、1、6 的子树仅包含自身，平均值等于节点值，均符合条件。 最终输出结果为 5。
二、解题思路
核心思路是后序遍历二叉树，因为计算子树的平均值需要先获取左、右子树的节点总和与节点数，再结合当前节点的值进行计算。具体步骤如下：
- 递归遍历左子树，获取左子树的节点总和与节点数。
- 递归遍历右子树，获取右子树的节点总和与节点数。
- 计算当前节点所在子树的总和（左子树总和 + 右子树总和 + 当前节点值）与节点数（左子树节点数 + 右子树节点数 + 1）。
- 计算子树平均值，判断是否与当前节点值相等，若相等则统计结果加 1。
- 将当前子树的总和与节点数返回给上层递归。
#include <iostream> #include <utility> using namespace std; // 二叉树节点定义 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 { private: int result = 0; // 统计符合条件的节点数 // 后序遍历辅助函数，返回当前子树的总和与节点数 pair<int, int> postOrder(TreeNode* root) { if (root == nullptr) { return {0, 0}; // 空节点返回总和0，节点数0 } // 递归遍历左子树 auto [leftSum, leftCount] = postOrder(root->left); // 递归遍历右子树 auto [rightSum, rightCount] = postOrder(root->right); // 计算当前子树的总和与节点数 int currentSum = leftSum + rightSum + root->val; int currentCount = leftCount + rightCount + 1; // 判断当前节点值是否等于子树平均值 if (root->val == currentSum / currentCount) { result++; } // 返回当前子树的总和与节点数给上层 return {currentSum, currentCount}; } public: int averageOfSubtree(TreeNode* root) { postOrder(root); return result; } }; // 测试代码 int main() { // 构建示例二叉树 TreeNode* root = new TreeNode(4); root->left = new TreeNode(8); root->right = new TreeNode(5); root->left->left = new TreeNode(0); root->left->right = new TreeNode(1); root->right->right = new TreeNode(6); Solution sol; cout << "符合条件的节点数：" << sol.averageOfSubtree(root) << endl; // 输出5 // 释放内存（可选，避免内存泄漏） delete root->left->left; delete root->left->right; delete root->right->right; delete root->left; delete root->right; delete root; return 0; }四、代码说明
- 二叉树节点结构：使用
TreeNode结构体定义二叉树节点，包含节点值、左子节点指针和右子节点指针。 - 后序遍历函数：
postOrder函数通过递归实现后序遍历，返回值为pair<int, int>，分别表示子树的总和与节点数。 - 统计逻辑：在计算完当前子树的总和与节点数后，判断节点值是否等于子树平均值，若相等则将
result加 1。 - 测试代码：构建题目示例中的二叉树，调用
averageOfSubtree函数并输出结果。
五、复杂度分析
- 时间复杂度：O (n)，其中 n 为二叉树的节点数，每个节点仅被遍历一次。
- 空间复杂度：O (h)，其中 h 为二叉树的高度，递归栈的深度取决于树的高度。
