Sponsored
Sponsored
This approach uses a recursive function to check if both trees are identical or one is a flipped version of the other. For each pair of nodes, we check if subtree structures match directly or with a flip.
Time Complexity: O(N), where N is the total number of nodes, since we visit each node once.
Space Complexity: O(H), where H is the height of the tree, due to the recursion stack.
1public class TreeNode {
2 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public TreeNode(int x) { val = x; }
6}
7
8public class Solution {
9 public bool FlipEquiv(TreeNode root1, TreeNode root2) {
10 if (root1 == null && root2 == null) return true;
11 if (root1 == null || root2 == null || root1.val != root2.val) return false;
12
13 return (FlipEquiv(root1.left, root2.left) &&
14 FlipEquiv(root1.right, root2.right)) ||
15 (FlipEquiv(root1.left, root2.right) &&
16 FlipEquiv(root1.right, root2.left));
17 }
18}This C# solution goes with the recursive comparison technique similar to other implementations, examining each node conditionally for normal or flipped child matches.
In this approach, instead of recursion, we use a stack for depth-first search. It proceeds similarly by evaluating if nodes are flip equivalent, but uses an explicit stack rather than the call stack.
Time Complexity: O(N).
Space Complexity: O(H), similar to the recursive approach.
1function TreeNode(val) {
2 this.val
The JavaScript implementation maintains a similar logic with a stack. By pushing nodes onto the stack and evaluating, this approach mimics the recursion virtually using an iterative style.