✨ Simple DFS || 3 Lines Solution || Beats 100% ✨
Intuition\nThe problem asks to determine if two binary trees are "flip equivalent." This means that the two trees are either structurally identical or can be ma
# Intuition\nThe problem asks to determine if two binary trees are "flip equivalent." This means that the two trees are either structurally identical or can be made identical by flipping some of the subtrees. My first thought is that I need to compare the two trees recursively, considering both the direct and the flipped cases at each node.\n\n# Approach\nWe can use a recursive depth-first search (DFS) to compare the two trees. For each node pair, there are two possibilities:\n1. The `left child` of the first tree matches the `left child` of the second tree, and the `right child` of the first tree matches the `right child` of the second tree.\n2. The `left child` of the first tree matches the `right child` of the second tree, and the `right child` of the first tree matches the `left child` of the second tree (flipped).\n\nThe base case for recursion is when both nodes are `nullptr` (in which case they are trivially equivalent), or when only one of the nodes is `nullptr` (in which case they are not equivalent). At each recursive step, we check if the current node values match, and we continue recursively down the children, considering both the direct and flipped cases.\n\n# Complexity\n- Time complexity:  \n  The time complexity is $$O(n)$$, where $$n$$ is the number of nodes in the smaller of the two trees. In the worst case, we have to traverse all the nodes in both trees to determine their equivalence.\n\n- Space complexity:  \n  The space complexity is $$O(h)$$, where $$h$$ is the height of the tree. This is due to the recursive call stack.\n\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 {\n    bool dfs(TreeNode* node1, TreeNode* node2) {\n        // If both nodes are null, they are equivalent\n        if(!node1 && !node2) return true;\n        // If only one is null, they are not equivalent\n        else if(!node1 || !node2) return false;\n\n        // Check if current nodes have the same value and \n        // (1) their children match directly or \n        // (2) their children match when flipped\n        return (node1->val == node2->val) && ((dfs(node1->left, node2->left) && dfs(node1->right, node2->right)) || (dfs(node1->left, node2->right) && dfs(node1->right, node2->left)));\n    }\npublic:\n    bool flipEquiv(TreeNode* root1, TreeNode* root2) {\n        return dfs(root1, root2);\n    }\n};\n```\n```java []\nclass Solution {\n    private boolean dfs(TreeNode node1, TreeNode node2) {\n        // If both nodes are null, they are equivalent\n        if (node1 == null && node2 == null) return true;\n        // If only one is null, they are not equivalent\n        if (node1 == null || node2 == null) return false;\n\n        // Check if current nodes have the same value and \n        // (1) their children match directly or \n        // (2) their children match when flipped\n        return node1.val == node2.val &&\n               ((dfs(node1.left, node2.left) && dfs(node1.right, node2.right)) || \n                (dfs(node1.left, node2.right) && dfs(node1.right, node2.left)));\n    }\n\n    public boolean flipEquiv(TreeNode root1, TreeNode root2) {\n        return dfs(root1, root2);\n    }\n}\n```\n```python []\nclass Solution:\n    def dfs(self, node1: TreeNode, node2: TreeNode) -> bool:\n        # If both nodes are null, they are equivalent\n        if not node1 and not node2:\n            return True\n        # If only one is null, they are not equivalent\n        if not node1 or not node2:\n            return False\n\n        # Check if current nodes have the same value and \n        # (1) their children match directly or \n        # (2) their children match when flipped\n        return (node1.val == node2.val and \n               ((self.dfs(node1.left, node2.left) and self.dfs(node1.right, node2.right)) or \n                (self.dfs(node1.left, node2.right) and self.dfs(node1.right, node2.left))))\n\n    def flipEquiv(self, root1: TreeNode, root2: TreeNode) -> bool:\n        return self.dfs(root1, root2)\n```\n```javascript []\nvar dfs = function(node1, node2) {\n    // If both nodes are null, they are equivalent\n    if (!node1 && !node2) return true;\n    // If only one is null, they are not equivalent\n    if (!node1 || !node2) return false;\n\n    // Check if current nodes have the same value and \n    // (1) their children match directly or \n    // (2) their children match when flipped\n    return node1.val === node2.val && \n           ((dfs(node1.left, node2.left) && dfs(node1.right, node2.right)) || \n            (dfs(node1.left, node2.right) && dfs(node1.right, node2.left)));\n};\n\nvar flipEquiv = function(root1, root2) {\n    return dfs(root1, root2);\n};\n```\n```golang []\nfunc dfs(node1 *TreeNode, node2 *TreeNode) bool {\n    // If both nodes are null, they are equivalent\n    if node1 == nil && node2 == nil {\n        return true\n    }\n    // If only one is null, they are not equivalent\n    if node1 == nil || node2 == nil {\n        return false\n    }\n\n    // Check if current nodes have the same value and \n    // (1) their children match directly or \n    // (2) their children match when flipped\n    return node1.Val == node2.Val &&\n        ((dfs(node1.Left, node2.Left) && dfs(node1.Right, node2.Right)) || \n         (dfs(node1.Left, node2.Right) && dfs(node1.Right, node2.Left)))\n}\n\nfunc flipEquiv(root1 *TreeNode, root2 *TreeNode) bool {\n    return dfs(root1, root2)\n}\n```\n```rust []\nimpl Solution {\n    fn dfs(node1: Option<&Box<TreeNode>>, node2: Option<&Box<TreeNode>>) -> bool {\n        match (node1, node2) {\n            (None, None) => true,\n            (Some(_), None) | (None, Some(_)) => false,\n            (Some(n1), Some(n2)) => {\n                n1.val == n2.val && \n                ((Solution::dfs(n1.left.as_ref(), n2.left.as_ref()) && \n                  Solution::dfs(n1.right.as_ref(), n2.right.as_ref())) || \n                 (Solution::dfs(n1.left.as_ref(), n2.right.as_ref()) && \n                  Solution::dfs(n1.right.as_ref(), n2.left.as_ref())))\n            }\n        }\n    }\n\n    pub fn flip_equiv(root1: Option<Box<TreeNode>>, root2: Option<Box<TreeNode>>) -> bool {\n        Solution::dfs(root1.as_ref(), root2.as_ref())\n    }\n}\n```\n\n![image.png](https://assets.leetcode.com/users/images/65c3cf30-71a1-44a0-8743-d97b33945d0b_1729385077.052562.png)\n
['Tree', 'Depth-First Search', 'Binary Tree', 'Python', 'C++', 'Java', 'Go', 'Python3', 'Rust', 'JavaScript']