951. Flip Equivalent Binary Trees

For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees.

A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations.

Write a function that determines whether two binary trees are flip equivalent. The trees are given by root nodes root1 and root2.

Example 1:

Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
Output: true
Explanation: We flipped at nodes with values 1, 3, and 5.

Note:

1. Each tree will have at most 100 nodes.

2. Each value in each tree will be a unique integer in the range [0, 99].

// Recursion
bool flipEquiv(TreeNode* root1, TreeNode* root2) { // time: O(N^2); space: O(height of tree)
    if (!root1 || !root2) return root1 == root2;
    if (root1->val != root2->val) return false;
    return (flipEquiv(root1->left, root2->left) && flipEquiv(root1->right, root2->right) ) || 
         (flipEquiv(root1->left, root2->right) && flipEquiv(root1->right, root2->left) );
}

// Iterative DFS
bool flipEquiv(TreeNode* root1, TreeNode* root2) { // time: O(n); space: O(n)
    stack<TreeNode*> st1({root1}), st2({root2});
    while (!st1.empty() && !st2.empty()) {
        TreeNode *n1 = st1.top(); st1.pop();
        TreeNode *n2 = st2.top(); st2.pop();
        if (!n1 && !n2) continue;
        else if (!n1 || !n2 || n1->val != n2->val) return false;
        if ((!n1->left && !n2->left) || (n1->left && n2->left && n1->left->val == n2->left->val)) {
            st1.push(n1->left);
            st1.push(n1->right);
            st2.push(n2->left);
            st2.push(n2->right);
        } else {
            st1.push(n1->right);
            st1.push(n1->left);
            st2.push(n2->left);
            st2.push(n2->right);
        }
    }
    return st1.empty() && st2.empty();
}

// Iterative BFS Level Order Traversal
bool isEqual(TreeNode* n1, TreeNode* n2) {
    if (!n1 || !n2) return n1 == n2;
    return n1->val == n2->val;
}
bool flipEquiv(TreeNode* root1, TreeNode* root2) { // time: (n); space: O(n)
    queue<TreeNode*> q;
    q.push(root1);
    q.push(root2);
    while (!q.empty()) {
        TreeNode *n1 = q.front(); q.pop();
        TreeNode *n2 = q.front(); q.pop();
        if (!n1 && !n2) continue;
        if (!isEqual(n1, n2)) return false;
        if (isEqual(n1->left, n2->left) && isEqual(n1->right, n2->right)) {
            q.push(n1->left);
            q.push(n2->left);
            q.push(n1->right);
            q.push(n2->right);
        } else if (isEqual(n1->left, n2->right) && isEqual(n1->right, n2->left)) {
            q.push(n1->left);
            q.push(n2->right);
            q.push(n1->right);
            q.push(n2->left);
        } else return false;
    }
    return true;
}