1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    private int ans;

    public int countUnivalSubtrees(TreeNode root) {
        if (root != null) {
            helper(root);
        }
        return ans;
    }

    private int helper(TreeNode node) {
        int leftTree = node.left == null ? node.val : helper(node.left);
        int rightTree = node.right == null ? node.val : helper(node.right);
        if (node.val == leftTree && node.val == rightTree) {
            ans += 1;
            return node.val;
        }
        return -2000;
    }
}

就是让所有的node都做root. 看该tree是否能构成满足题意的subtree. 我们需要知道左右支是否是满足题意的subtree, 如果是的话值是多少. 需要考虑的一个点就是如果某个支是null, 那么我们也认为这是符合题意的, 但是它没有自己的值. 于是我们还要手动不走到node是null的情况, 如果发现某一支是null, 我们就手动记录这一支的值是当前node的val. 递归函数返回的如果是正数, 就说明该支是valid的substree并且值是这个正数, 如果不是, 那返回一个负数, 但这个数字不能等于node.val可能出现的值, 于是我们根据题目上说的node.val的范围, 直接返回-2000.

为什么会想到这个思路? 因为我们发现当只有一个node的时候, 我们是可以直接得到答案的. 于是就萌生了从leaf往上帮各个node确认自己是否为valid的substree的想法.

时间复杂度: O(n)
空间复杂度: O(n)