Leetcode 1612 Check If Two Expression Trees are Equivalent

Problem statement

https://leetcode.com/problems/check-if-two-expression-trees-are-equivalent/

Solution

Traverse trees and count number of times we meet each symbol.

Complexity

Time complexity is O(26n + 26m), where n and m are sizes of our trees. Space complexity is O(26*max(h1, h2)), where h1 and h2 are heights of our trees.

Code

class Solution:
    def checkEquivalence(self, root1, root2):
        def dfs(node):
            if node.val != "+": return Counter(node.val)
            return dfs(node.left) + dfs(node.right)
        
        return dfs(root1) == dfs(root2)