951. Flip Equivalent Binary Trees

MediumView on LeetCode

Tree Depth-First Search Binary Tree

Time: O(n)

Space: O(n)

Intuition

Two trees are flip-equivalent if one can be made identical to the other by flipping some node children.

Algorithm

1DFS: base cases (both null, one null, different values).
2Return (flipEquiv(l1,l2) && flipEquiv(r1,r2)) || (flipEquiv(l1,r2) && flipEquiv(r1,l2)).

Common Pitfalls

•Check both direct and flipped child combinations.

951.cs

// Approach: Recursive equivalence check; two trees are flip-equivalent if they match directly or after swapping children at any node.
// Time: O(n) Space: O(n)

public class TreeNode(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);
    }
}

Was this solution helpful?