LeetCode Solutions

951. Flip Equivalent Binary Trees

Time: $O(n)$

Space: $O(h)$

			

class Solution {
 public:
  bool flipEquiv(TreeNode* root1, TreeNode* root2) {
    if (root1 == nullptr)
      return root2 == nullptr;
    if (root2 == nullptr)
      return root1 == nullptr;
    if (root1->val != root2->val)
      return false;
    return flipEquiv(root1->left, root2->left) &&
               flipEquiv(root1->right, root2->right) ||
           flipEquiv(root1->left, root2->right) &&
               flipEquiv(root1->right, root2->left);
  }
};
			

class Solution {
  public boolean flipEquiv(TreeNode root1, TreeNode root2) {
    if (root1 == null)
      return root2 == null;
    if (root2 == null)
      return root1 == null;
    if (root1.val != root2.val)
      return false;
    return flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right) ||
           flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left);
  }
}
			

class Solution:
  def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
    if not root1:
      return not root2
    if not root2:
      return not root1
    if root1.val != root2.val:
      return False
    return self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right) or \
        self.flipEquiv(root1.left, root2.right) and self.flipEquiv(
        root1.right, root2.left)