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 <iostream>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9};
10
11class Solution {
12public:
13 bool flipEquiv(TreeNode* root1, TreeNode* root2) {
14 if (!root1 && !root2) return true;
15 if (!root1 || !root2 || root1->val != root2->val) return false;
16
17 return (flipEquiv(root1->left, root2->left) &&
18 flipEquiv(root1->right, root2->right)) ||
19 (flipEquiv(root1->left, root2->right) &&
20 flipEquiv(root1->right, root2->left));
21 }
22};This C++ code uses a class-based approach where the method flipEquiv is defined to recursively compare nodes in both trees for equivalency, considering normal and flipped child nodes.
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.
1class TreeNode:
2 def __init__(self, x)
In this Python implementation, we use a stack to iteratively check node pairs. We continue popping nodes to compare for equivalency in both standard and flipped orientations until the stack is empty.