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.
1class TreeNode {
2 int val;
3 TreeNode left;
4 TreeNode right;
5 TreeNode(int x) { val = x; }
6}
7
8class Solution {
9 public boolean 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}In the Java solution, we implement the recursive check in the Solution class. This method checks each node and its children for equivalency without and with flips.
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.