0ms C++,Rust |  DFS Solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\nclass Solution {\npublic:\n    bool flipEquiv(TreeNode* root1, TreeNode* root2) {\n        if(root1==0&&root2==0) return true;\n        if(!(root1&&root2))return false;\n        if(root1->val==root2->val) {\n            bool f1=flipEquiv(root1->left,root2->left)&&flipEquiv(root1->right,root2->right);\n            if(f1) return true;\n            bool f2=flipEquiv(root1->right,root2->left)&&flipEquiv(root1->left,root2->right);\n            if(f2) return true;\n        }\n        return false;\n    }\n};\n```\n```rust []\n// Definition for a binary tree node.\n// #[derive(Debug, PartialEq, Eq)]\n// pub struct TreeNode {\n//   pub val: i32,\n//   pub left: Option<Rc<RefCell<TreeNode>>>,\n//   pub right: Option<Rc<RefCell<TreeNode>>>,\n// }\n// \n// impl TreeNode {\n//   #[inline]\n//   pub fn new(val: i32) -> Self {\n//     TreeNode {\n//       val,\n//       left: None,\n//       right: None\n//     }\n//   }\n// }\nuse std::rc::Rc;\nuse std::cell::RefCell;\nimpl Solution {\n    pub fn flip_equiv(root1: Option<Rc<RefCell<TreeNode>>>, root2: Option<Rc<RefCell<TreeNode>>>) -> bool {\n        if root1.is_none()&&root2.is_none() {\n            return true;\n        }\n        if let Some(root1)=root1 {\n            if let Some(root2)=root2 {\n                let v1=root1.borrow().val;\n                let v2=root2.borrow().val;\n                if v1!=v2 {\n                    return false;\n                }\n                let l1=&root1.borrow().left;\n                let r1=&root1.borrow().right;\n                let l2=&root2.borrow().left;\n                let r2=&root2.borrow().right;\n                let f1=Self::flip_equiv(l1.clone(),l2.clone())&&Self::flip_equiv(r1.clone(),r2.clone());\n                if f1 { return true;}\n                let f2=Self::flip_equiv(r1.clone(),l2.clone())&&Self::flip_equiv(l1.clone(),r2.clone());\n                if f2 {return true;}\n            }\n        }\n        return false;\n    }\n}\n```
['Tree', 'Depth-First Search', 'Recursion', 'Binary Tree', 'C++', 'Rust']