Problem statement

https://binarysearch.com/problems/Univalue-Tree-Count/

Solution

Use dfs with state (if subtree is good, value of this subtree). Second value can be anything if subtree is not good.

Complexity

It is O(n) for time and O(h) for space.

Code

class Solution:
    def solve(self, root):
        self.ans = 0
        def dfs(node):
            x, vals = [True], [node.val]
            for child in filter(None, [node.left, node.right]):
                ans1, val1 = dfs(child)
                vals += [val1]
                x += [ans1]

            if False not in x and len(set(vals)) == 1:
                self.ans += 1
                return [True, vals[0]]
            else:
                return [False, 0]

        dfs(root)
        return self.ans