[LintCode] Problem 921 - Count Univalue Subtrees

Posted on | In ,

Given a binary tree, count the number of uni-value subtrees.

A Uni-value subtree means all nodes of the subtree have the same value.

Example

No.1

Input: root = {5,1,5,5,5,#,5}

Output: 4

Explanation:

1
2
3
4
5
    5
   / \
  1   5
 / \   \
5   5   5

No.2

Input: root = {1,3,2,4,5,#,6}

Output: 3

Explanation:

1
2
3
4
5
    1
   / \
  3   2
 / \   \
4   5   6

Code

1
2
3
4
5
6
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private int count = 0;

public int countUnivalSubtrees(TreeNode root) {
    countHelper(root, -1);
    return count;
}

private boolean countHelper(TreeNode root, int parent) {
    if (root == null)
        return true;

    boolean left = countHelper(root.left, root.val);
    boolean right = countHelper(root.right, root.val);

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

    count++;
    return root.val == parent;
}