Flip Equivalent Binary Trees

Problem Id: 951 Difficulty: Medium Tag: Tree


Intuition

We could use <=> to represent flip equivalent.

X <=> Y if and only if X.left <=> Y.left and X.right <=> Y.right, or X.left <=> Y.right and X.right <=> Y.left. So we could use this to solve this problem recursivly.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def flipEquiv(self, root1: TreeNode, root2: TreeNode) -> bool:
        if root1 is None and root2 is None:
            return True
        elif root1 is None or root2 is None:
            return False
        elif root1.val != root2.val:
            return False

        if self.flipEquiv(root1.left, root2.left) and \
                self.flipEquiv(root1.right, root2.right):
            return True
        elif self.flipEquiv(root1.left, root2.right) and \
                self.flipEquiv(root1.right, root2.left):
            return True
        return False