5.22 Count Univalue Subtrees

5.22.1 Problem Metadata

• Platform: LeetCode
• Problem ID: 250
• Difficulty: Medium
• URL: https://leetcode.com/problems/count-univalue-subtrees/
• Tags:
• Techniques: Depth First Search, Recursion, Tree

5.22.2 Description

Count subtrees where every node has the same value.

5.22.3 Solution - DFS

5.22.3.1 Walkthrough

Traverse bottom-up and return whether each subtree is univalue. A node is univalue if both children are univalue and (when present) match the current node’s value. Count each node that satisfies the condition.

5.22.3.2 Analysis

• Time Complexity: O(n)
• Space Complexity: O(h)

5.22.3.3 Code - Java

public int countUnivalSubtrees(TreeNode root) {
    int[] count = new int[1];
    dfs(root, count);
    return count[0];
}

private boolean dfs(TreeNode node, int[] count) {
    if (node == null) {
        return true;
    }
    boolean left = dfs(node.left, count);
    boolean right = dfs(node.right, count);
    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;
    }
    count[0]++;
    return true;
}