Problem statement

https://binarysearch.com/problems/Inverted-Subtree/

Solution

We can evaluate so-called canonical representation of tree: evaluate answers for left and right and use left before right.

Complexity

It is O(n^2) for time and O(n) for space.

Code

class Solution:
    def solve(self, s, t):
        def dfs(root):
            if not root: return "#"
            L, R = dfs(root.left), dfs(root.right)
            L, R = min(L, R), max(L, R)
            return str(root.val) + ":" + L + ":" + R
        return ":" + dfs(s) in ":" + dfs(t)