Skip to content

951. Flip Equivalent Binary Trees 👍

  • Time: $O(n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def flipEquiv(self, root1: TreeNode | None, root2: TreeNode | None) -> 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))