Flip equivalent binary trees

Tree Depth-First Search Binary Tree

69.6% acceptance

Feb 27, 2026

2882

123

For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees. A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations. Given the roots of two binary trees root1 and root2, return true if the two trees are flip equivalent or false otherwise.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
// 
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn flip_equiv(root1: Option<std::rc::Rc<std::cell::RefCell<TreeNode>>>, root2: Option<std::rc::Rc<std::cell::RefCell<TreeNode>>>) -> bool {
    match (root1, root2) {
      (None, None) => true,
      (Some(n1), Some(n2)) => {
        let n1 = n1.borrow();
        let n2 = n2.borrow();
        if n1.val != n2.val { return false; }
        // no flip
        let no_flip = Self::flip_equiv(n1.left.clone(), n2.left.clone())
          && Self::flip_equiv(n1.right.clone(), n2.right.clone());
        // flip
        let flip = Self::flip_equiv(n1.left.clone(), n2.right.clone())
          && Self::flip_equiv(n1.right.clone(), n2.left.clone());
        no_flip || flip
      }
      _ => false,
    }
  }
}