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 def __init__(self, x):
3 self.val = x
4 self.left = None
5 self.right = None
6
7class Solution:
8 def flipEquiv(self, root1: TreeNode, root2: TreeNode) -> bool:
9 if not root1 and not root2:
10 return True
11 if not root1 or not root2 or root1.val != root2.val:
12 return False
13
14 return (self.flipEquiv(root1.left, root2.left) and
15 self.flipEquiv(root1.right, root2.right)) or
16 (self.flipEquiv(root1.left, root2.right) and
17 self.flipEquiv(root1.right, root2.left))Here, the Python implementation follows the recursive checking strategy using a Solution class method. It checks the required conditions at each node to ascertain if the trees are flip equivalent.
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.