0250. Count Univalue Subtrees

Medium | Binary Tree + DFS | 24 ms (99.41%), 14.4 MB (72.31%)

❓ Problem Statement

Source: LeetCode - Count Univalue Subtrees GitHub: Solution / Performance

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

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

✍🏻 Constraints & Example

Constraints:

• The numbrt of the node in the tree will be in the range [0, 1000].

• -1000 <= Node.val <= 1000

💡 Ideas

To check all nodes of the subtree, we need to adopt the DFS method since we cannot finalize the answer until all nodes are visited.

First, note that leaf nodes have a valid uni-value subtree.

To make sure an internal node has a valid uni-value subtree, we pass parent nodes' values into the DFS iteration of child nodes to check.

In each DFS iteration, we first check whether the left- and right- nodes have uni-value subtrees. Then, we use the parent node's value to compare with the current node's value.

🤖 Python

class Solution:
    def countUnivalSubtrees(self, root: TreeNode) -> int:
        # (base case)
        if not root: return 0
        if not root.left and not root.right: return 1
        
        # ==================================================
        #  Binary Search Tree + DFS                        =
        # ==================================================
        # time  : O(n)
        # space : O(H)

        self.unival = 0
        self.dfs(root, root.val)
        
        return self.unival
        
    def dfs(self, node: TreeNode, preVal: int) -> bool:
        if not node: return True
        
        left  = self.dfs(node.left,  node.val)
        right = self.dfs(node.right, node.val)
        
        if not left or not right:
            return False
        
        self.unival += 1
        
        return node.val == preVal

🤖 Java

class Solution {
    /**
     * @time  : O(n)
     * @space : O(H)
     */

    int count = 0;

    public int countUnivalSubtrees(TreeNode root) {
        /* base case */
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;
        
        dfs(root, root.val);
        return count;
    }
    
    private boolean dfs(TreeNode node, int val) {
        if (node == null)
            return true;
        
        boolean left  = dfs(node.left, node.val);
        boolean right = dfs(node.right, node.val);
        
        if(!left || !right)
            return false;
        
        count++;
        
        return node.val == val;
    }
}