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)
      return !root2;
    if (!root2)
      return !root1;
    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 {
  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
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)