<p>For a binary tree <strong>T</strong>, we can define a <strong>flip operation</strong> as follows: choose any node, and swap the left and right child subtrees.</p><p>A binary tree <strong>X</strong> is <strong>flip equivalent</strong> to a binary tree <strong>Y</strong> if and only if we can make <strong>X</strong> equal to <strong>Y</strong> after some number of flip operations.</p><p>Given the roots of two binary trees <code>root1</code> and <code>root2</code>, return <code>true</code> if the two trees are flip equivalent or <code>false</code> otherwise.</p>
Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]Output: trueExplanation: We flipped at nodes with values 1, 3, and 5.
<ul>
<li>The number of nodes in each tree is in the range <code>[0, 100]</code>.</li>
<li>Each tree will have <strong>unique node values</strong> in the range <code>[0, 99]</code>.</li>
</ul>
from leetcode_py import TreeNodeclass Solution: # Time: O(n) # Space: O(h) where h is the tree height def flip_equiv(self, root1: TreeNode[int] | None, root2: TreeNode[int] | None) -> bool: if root1 is None or root2 is None: return root1 is root2 if root1.val != root2.val: return False no_flip = self.flip_equiv(root1.left, root2.left) and self.flip_equiv( root1.right, root2.right ) flip = self.flip_equiv(root1.left, root2.right) and self.flip_equiv(root1.right, root2.left) return no_flip or flip
