统计值等于子树平均值的节点数 图解题解

这道题到底在问什么

输入

root=[54,40,88,30,51,25,95]

输出

6

输入

root=[1]

输出

1

最优解：一步一步想明白

1. 3记牢这一句:先递归到最底下,再一层层往上把和与个数带回来,在每个节点顺手算一次平均、比一次值。下面从根出发,一路下探到叶子,再自底向上回算。
2. 4从根出发向下递归先看清这棵树的形状。后序遍历的规矩是:不急着在半路结算,而是一头扎到最底下的叶子,从叶子开始把子树的和与个数一层层往上抬。你盯住紫色,它代表当前正在处理的节点;绿色代表已经验过、达标的节点;红色代表验过但不达标的节点。现在从根出发往下走。
3. 5空树: sum = 0, n = 0正式下探前先说好一个约定:走到空位置,也就是没有节点的地方,直接返回和 0、个数 0,它什么都不贡献。有了这条,叶子的左右孩子都是空,回来都是 0 加 0,叶子的子树和就只剩它自己,个数就是 1,天然成立。这条约定是整个递归能自底向上算对的地基。
4. 6先递归它的左子树走到值 54 的节点,它下面还挂着孩子,现在还不能结算。按后序的规矩,得先把它的左子树整个算完、右子树整个算完,拿到两边的和与个数,才轮到它自己。先钻左子树。
5. 7先递归它的左子树走到值 40 的节点,它下面还挂着孩子,现在还不能结算。按后序的规矩,得先把它的左子树整个算完、右子树整个算完,拿到两边的和与个数,才轮到它自己。先钻左子树。
6. 8值 30 是叶子走到值 30 的节点,它没有孩子,是个叶子。叶子这一步最省事:它的子树就它自己一个,和就是 30,个数是 1。下一帧直接给它结算。
7. 9平均 = 30,达标结算值 30 的这个叶子。子树只有它自己,和是 30,个数是 1,平均就是 30 除以 1 等于 30。这个平均正好等于节点自己的值 30,达标,把它标绿,达标节点数变成 1。它向上返回的就是一对数字:和 30、个数 1。
8. 10左子树算完,再递归右子树值 40 的左子树整个算完了,左边带回来的是:和 30、个数 1。但现在还不能拍板,右子树还没碰。回到值 40,接着钻它的右子树,把右边那对数字也拿回来。
9. 11值 51 是叶子走到值 51 的节点,它没有孩子,是个叶子。叶子这一步最省事:它的子树就它自己一个,和就是 51,个数是 1。下一帧直接给它结算。
10. 12平均 = 51,达标结算值 51 的这个叶子。子树只有它自己,和是 51,个数是 1,平均就是 51 除以 1 等于 51。这个平均正好等于节点自己的值 51,达标,把它标绿,达标节点数变成 2。它向上返回的就是一对数字:和 51、个数 1。
11. 13和 121 · 个数 3左右子树都回来了。值 40 把两边的和加上自己的值:30 加 51 加 40,等于 121;个数是左边 1 加右边 1 再加自己这一个,等于 3。这就是值 40 整棵子树的和与个数,下一帧拿它算平均。
12. 14平均 = 40,达标给值 40 结算。平均值等于和 121 除以个数 3。算出来是 40.33,向下取整拿 40。这个 40 恰好等于节点自己的值 40,达标,标绿,达标节点数变成 3。不管达不达标,它都要照常把和 121、个数 3 向上返回给父节点。
13. 15左子树算完,再递归右子树值 54 的左子树整个算完了,左边带回来的是:和 121、个数 3。但现在还不能拍板,右子树还没碰。回到值 54,接着钻它的右子树,把右边那对数字也拿回来。
14. 16先递归它的左子树走到值 88 的节点,它下面还挂着孩子,现在还不能结算。按后序的规矩,得先把它的左子树整个算完、右子树整个算完,拿到两边的和与个数,才轮到它自己。先钻左子树。
15. 17值 25 是叶子走到值 25 的节点,它没有孩子,是个叶子。叶子这一步最省事:它的子树就它自己一个,和就是 25,个数是 1。下一帧直接给它结算。
16. 18平均 = 25,达标结算值 25 的这个叶子。子树只有它自己,和是 25,个数是 1,平均就是 25 除以 1 等于 25。这个平均正好等于节点自己的值 25,达标,把它标绿,达标节点数变成 4。它向上返回的就是一对数字:和 25、个数 1。
17. 19左子树算完,再递归右子树值 88 的左子树整个算完了,左边带回来的是:和 25、个数 1。但现在还不能拍板,右子树还没碰。回到值 88,接着钻它的右子树,把右边那对数字也拿回来。
18. 20值 95 是叶子走到值 95 的节点,它没有孩子,是个叶子。叶子这一步最省事:它的子树就它自己一个,和就是 95,个数是 1。下一帧直接给它结算。
19. 21平均 = 95,达标结算值 95 的这个叶子。子树只有它自己,和是 95,个数是 1,平均就是 95 除以 1 等于 95。这个平均正好等于节点自己的值 95,达标,把它标绿,达标节点数变成 5。它向上返回的就是一对数字:和 95、个数 1。
20. 22和 208 · 个数 3左右子树都回来了。值 88 把两边的和加上自己的值:25 加 95 加 88,等于 208;个数是左边 1 加右边 1 再加自己这一个,等于 3。这就是值 88 整棵子树的和与个数,下一帧拿它算平均。
21. 23平均 = 69,不达标给值 88 结算。平均值等于和 208 除以个数 3。算出来是 69.33,向下取整拿 69。这个 69 并不等于节点自己的值 88,不达标,标红,达标节点数不加,仍是 5。不管达不达标,它都要照常把和 208、个数 3 向上返回给父节点。
22. 24和 383 · 个数 7左右子树都回来了。值 54 把两边的和加上自己的值:121 加 208 加 54,等于 383;个数是左边 3 加右边 3 再加自己这一个,等于 7。这就是值 54 整棵子树的和与个数,下一帧拿它算平均。
23. 25平均 = 54,达标给值 54 结算。平均值等于和 383 除以个数 7。算出来是 54.71,向下取整拿 54。这个 54 恰好等于节点自己的值 54,达标,标绿,达标节点数变成 6。不管达不达标,它都要照常把和 383、个数 7 向上返回给父节点。
24. 26答案 = 6整棵树验完了。四个叶子 30、51、25、95 各自子树只有自己,平均等于自己,全达标;值 40 的子树平均 40、值 54 的子树平均 54,也都对得上,达标;唯独值 88 的子树平均是 69,不等于 88,不达标,标红。数一数绿色节点,一共 6 个,这就是答案。判定始终只做一件事:在每个节点算子树平均、和它自己的值比一比。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
from string import *
from operator import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def averageOfSubtree(self, root: TreeNode) -> int:
        def dfs(root) -> tuple:
            if not root:
                return 0, 0
            ls, ln = dfs(root.left)
            rs, rn = dfs(root.right)
            s = ls + rs + root.val
            n = ln + rn + 1
            nonlocal ans
            ans += int(s // n == root.val)
            return s, n

        ans = 0
        dfs(root)
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
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) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * 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 ans = 0;
        function<pair<int, int>(TreeNode*)> dfs = [&]( TreeNode* root ) -> pair<int, int> {
            if (!root) {
                return {0, 0};
            }
            auto [ls, ln] = dfs(root->left);
            auto [rs, rn] = dfs(root->right);
            int s = ls + rs + root->val;
            int n = ln + rn + 1;
            if (s / n == root->val) {
                ++ans;
            }
            return {s, n};
        };
        dfs(root);
        return ans;
    }
};

import java.util.*;
/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
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;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private int ans;

    public int averageOfSubtree(TreeNode root) {
        ans = 0;
        dfs(root);
        return ans;
    }

    private int[] dfs(TreeNode root) {
        if (root == null) {
            return new int[2];
        }
        int[] l = dfs(root.left);
        int[] r = dfs(root.right);
        int s = l[0] + r[0] + root.val;
        int n = l[1] + r[1] + 1;
        if (s / n == root.val) {
            ++ans;
        }
        return new int[] {s, n};
    }
}

复杂度

面试官可能追问