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.
1function TreeNode(val) {
2 this.val = val;
3 this.left = this.right = null;
4}
5
6var flipEquiv = function(root1, root2) {
7 if (!root1 && !root2) return true;
8 if (!root1 || !root2 || root1.val !== root2.val) return false;
9
10 return (flipEquiv(root1.left, root2.left) &&
11 flipEquiv(root1.right, root2.right)) ||
12 (flipEquiv(root1.left, root2.right) &&
13 flipEquiv(root1.right, root2.left));
14};JavaScript is used to create a recursive function flipEquiv which does the node comparison. It looks at whether nodes are equivalent either directly or by flipping the children.
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.