LeetCode 250. 统计同值子树

2026-09-13 HGNULB 约 4 分钟

文章信息 2 个分类 3 个标签

分类

LeetCode 中等

题目描述

✅ 250. 统计同值子树

题意分析

统计二叉树中有多少棵同值子树。一棵子树由某个节点及它的全部后代组成，只有这些节点的值全部相同才合格，不能从里面挑掉不相同的分支后再算。

每个节点作为根对应一棵候选子树，同值子树之间可以彼此包含，需要分别计数。单个叶子一定合格，空树不贡献数量。题目求的是子树数量，不是最大同值区域大小或最长同值路径。

解法：后序返回同值状态并累计数量

核心思路

[!blue]

用后序递归先判断左右子树，再判断当前节点对应的整棵子树。same(node) 的返回值只表示这一整棵子树是否同值，全局或闭包中的 answer 则负责累计已经发现的所有合格子树，两种信息不能混为一谈。

当前子树同值，需要同时满足两个条件：左右子树各自同值；每个非空孩子的值都等于当前节点值。如果一个孩子的整棵子树已经同值，它的根值就代表那一侧的全部节点值，再与当前值比较便足够，不需要重新扫描该分支。

空节点返回真，表示不存在的分支不会破坏父节点的同值条件，但它在返回前不会增加答案。叶子的两侧都为空，因而自然通过所有检查，给答案加一。内部节点也只有全部条件通过后才加一，并返回真。

必须先分别执行左右递归，再合并布尔结果。即使左子树不同值，右子树中仍可能包含许多合格子树，需要继续统计；若将两个递归调用直接写进逻辑与，左侧为假时短路会跳过右边的遍历。

某个节点最终返回假，只是否定以它为根的完整子树，不会撤销它下面已经累计的合格数量。入口每次重新将计数清零，完成全部递归后返回累计值，而不是只查看整棵树的布尔判定。

解题步骤

初始化答案为零，从根调用同值判定函数。

空节点返回真，不增加计数。

分别递归左右孩子，确保两侧统计都完成。

两侧状态都真且非空孩子值都等于当前值时，答案加一并返回真；否则返回假。

递归结束后返回累计答案。

代码实现

class Solution {
    private int answer;

    public int countUnivalSubtrees(TreeNode root) {
        answer = 0;
        same(root);

        return answer;
    }

    private boolean same(TreeNode node) {
        if (node == null) {
            return true;
        }

        boolean left = same(node.left);
        boolean right = same(node.right);

        if (!left || !right) {
            return false;
        }

        if (node.left != null && node.left.val != node.val) {
            return false;
        }

        if (node.right != null && node.right.val != node.val) {
            return false;
        }

        answer++;

        return true;
    }
}

func countUnivalSubtrees(root *TreeNode) int {
    answer := 0
    var same func(*TreeNode) bool
    same = func(node *TreeNode) bool {
        if node == nil {
            return true
        }
        left, right := same(node.Left), same(node.Right)
        if !left || !right {
            return false
        }
        if node.Left != nil && node.Left.Val != node.Val {
            return false
        }
        if node.Right != nil && node.Right.Val != node.Val {
            return false
        }
        answer++
        return true
    }
    same(root)
    return answer
}

复杂度分析

时间复杂度：$O(n)$，每个节点只进行一次后序合并，不为每棵候选子树重复扫描全部后代。

空间复杂度：$O(h)$，h 为树高，来自递归栈，计数器为常数空间。

关键点总结

[!green]

返回值描述当前完整子树，累计值包含此前所有合格子树。

子树状态与父子值关系共同决定当前是否合格，只比较直接孩子不够。

左右递归必须都执行，布尔合并可以短路，带统计副作用的遍历不能被跳过。

易错点总结

[!yellow]

将左右递归直接放进 &&，左侧失败时会漏掉右侧内部的统计。

只检查直接父子值相等，忽略更深后代可能不同。

把空节点返回真理解成空树也要计数，会多算不存在的子树。

只统计最大同值区域，漏掉其中以不同节点为根的更小合格子树。

当前整棵树不同值就把答案归零，会丢掉已经找到的内部合格子树。

Java 复用同一对象时不重置成员计数，会把多次调用的结果累计到一起。

相似题目

题目	难度	关联与区别
687. 最长同值路径	中等	同样后序检查父子值是否相等；原题返回最长同值路径，本题要求整棵子树全部同值。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/46440889

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！