D
DevExCode

LeetCode 250: Count Univalue Subtrees Solution

Master LeetCode problem 250 (Count Univalue Subtrees), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

250. Count Univalue Subtrees

Medium
TreeDepth-First SearchBinary Tree

Problem Explanation

Explanation:

To solve this problem, we can perform a bottom-up approach using recursion. We will traverse the tree in a post-order manner and check if each subtree is a univalue subtree. A subtree is considered a univalue subtree if all nodes in the subtree have the same value.

  1. We define a recursive function countUnivalSubtrees that returns a boolean indicating if the subtree rooted at the current node is a univalue subtree, along with the count of univalue subtrees found in the subtree.
  2. We recursively call the function on the left and right children of the current node.
  3. If both the left and right subtrees are univalue subtrees and the current node's value is equal to its children's values (if present), then we increment the count and return true.
  4. Otherwise, we return false.

Time Complexity: O(N) - where N is the number of nodes in the tree Space Complexity: O(H) - where H is the height of the tree

Solution Code

class Solution {
    int count = 0;
    
    public int countUnivalSubtrees(TreeNode root) {
        isUnivalSubtree(root);
        return count;
    }
    
    private boolean isUnivalSubtree(TreeNode node) {
        if (node == null) {
            return true;
        }
        
        boolean left = isUnivalSubtree(node.left);
        boolean right = isUnivalSubtree(node.right);
        
        if ((node.left == null || node.left.val == node.val) && 
            (node.right == null || node.right.val == node.val) &&
            left && right) {
            count++;
            return true;
        }
        
        return false;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 250 (Count Univalue Subtrees)?

This page provides optimized solutions for LeetCode problem 250 (Count Univalue Subtrees) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 250 (Count Univalue Subtrees)?

The time complexity for LeetCode 250 (Count Univalue Subtrees) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 250 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 250 in Java, C++, or Python.

Back to LeetCode Solutions