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.
1#include <stdbool.h>
2
3struct TreeNode {
4 int val;
5 struct TreeNode *left;
6 struct TreeNode *right;
7};
8
9bool flipEquiv(struct TreeNode* root1, struct TreeNode* root2) {
10 if (!root1 && !root2) return true;
11 if (!root1 || !root2 || 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}In this C implementation, a recursive function flipEquiv is called for each node. It first checks base cases, including if both nodes are null (return true), or if one is null and the other isn't (return false). Then it checks if the current nodes are equal in value and recursively checks for their children in both non-flipped and flipped scenarios.
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.