250. Count Univalue Subtrees

, 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int countUnivalSubtrees(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int count = 0;
        count += countUnivalSubtrees(root.left);
        count += countUnivalSubtrees(root.right);

        count += isSameValueTree(root) ? 1 : 0;

        return count;
    }

    private boolean isSameValueTree(TreeNode root) {
        if (root == null) {
            return true; // 注意此处返回 true, 即到达了空节点说明只有同值才能到达
        }

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

        return isSameValueTree(root.left) && isSameValueTree(root.right);
    }
}

References

250. Count Univalue Subtrees