C# Solution for Flip Equivalent Binary Trees Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem of checking whether two binary trees are flip equivalent comes from the obs
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem of checking whether two binary trees are flip equivalent comes from the observation that at each node, we can either:\n\n\u2022\tLeave the subtrees as they are.\n\u2022\tFlip the subtrees and compare.\n\nThe goal is to determine if the two binary trees can be made identical by applying a sequence of these flip operations at various nodes. Since flipping can occur at any node, we need a recursive approach that considers both the flipped and unflipped scenarios.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tBase cases:\n\t\u2022\tIf both nodes are null, the trees are trivially equivalent, so return true.\n\t\u2022\tIf one node is null but the other is not, or if their values differ, the trees cannot be equivalent, so return false.\n2.\tRecursive checks:\n\t\u2022\tFirst, check if the left subtree of one tree is flip equivalent to the left subtree of the other and the right subtree is equivalent without flipping.\n\t\u2022\tThen, check if flipping the subtrees results in equivalence (i.e., if the left subtree of one tree is flip equivalent to the right subtree of the other and vice versa).\n3.\tReturn the result:\n\t\u2022\tIf either the non-flip or flip condition is satisfied at any node, the trees are flip equivalent.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\u2022\tO(n), where n is the number of nodes in the smaller of the two trees (or either tree if they have the same number of nodes).\n\u2022\tWhy: We traverse both trees simultaneously, visiting each node exactly once. For each node, we make constant-time comparisons and recursive calls to its children, so the overall time complexity is linear with respect to the number of nodes.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\u2022\tO(h), where h is the height of the tree.\n\u2022\tWhy: This is the space used by the recursion stack. In the worst case, the recursion depth is proportional to the height of the tree. For a completely unbalanced tree, the height can be as large as n, making the space complexity O(n). For a balanced tree, the height is O(log n), so the space complexity is O(log n).\n\n# Code\n```csharp []\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     public int val;\n *     public TreeNode left;\n *     public TreeNode right;\n *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n */\npublic class Solution {\n    public bool FlipEquiv(TreeNode root1, TreeNode root2) {\n        if (root1 == null && root2 == null) return true;\n        if (root1 == null || root2 == null || root1.val != root2.val) return false;\n        bool noFlip = FlipEquiv(root1.left, root2.left) && FlipEquiv(root1.right, root2.right);\n        bool flip = FlipEquiv(root1.left, root2.right) && FlipEquiv(root1.right, root2.left);\n        return noFlip || flip;\n    }\n}\n```
['C#']