LeetCodee

951. Flip Equivalent Binary Trees

Jump to Solution: Python Java C++ JavaScript C#

Problem Description

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.

Given the roots of two binary trees root1 and root2, return true if the two trees are flip equivalent or false otherwise.

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.

Example 2:

Input: root1 = [], root2 = []
Output: true

Example 3:

Input: root1 = [], root2 = [1]
Output: false

Constraints:

  • The number of nodes in each tree is in the range [0, 100].
  • Each tree will have unique node values in the range [0, 99].

Solution

Python Solution

class Solution:
    def flipEquiv(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        if not root1 and not root2:
            return True
        if not root1 or not root2 or root1.val != root2.val:
            return False
        
        # Check if current nodes are equal without flipping
        if self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right):
            return True
        
        # Check if current nodes are equal after flipping
        if self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left):
            return True
        
        return False

Time Complexity: O(min(N1, N2))

Where N1 and N2 are the number of nodes in the two trees. We visit each node at most once.

Space Complexity: O(min(H1, H2))

Where H1 and H2 are the heights of the two trees. The recursion stack can go as deep as the height of the smaller tree.

Java Solution

class Solution {
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return true;
        }
        if (root1 == null || root2 == null || root1.val != root2.val) {
            return false;
        }
        
        // Check if current nodes are equal without flipping
        if (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right)) {
            return true;
        }
        
        // Check if current nodes are equal after flipping
        if (flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left)) {
            return true;
        }
        
        return false;
    }
}

Time Complexity: O(min(N1, N2))

Where N1 and N2 are the number of nodes in the two trees. We visit each node at most once.

Space Complexity: O(min(H1, H2))

Where H1 and H2 are the heights of the two trees. The recursion stack can go as deep as the height of the smaller tree.

C++ Solution

class Solution {
public:
    bool flipEquiv(TreeNode* root1, TreeNode* root2) {
        if (!root1 && !root2) {
            return true;
        }
        if (!root1 || !root2 || root1->val != root2->val) {
            return false;
        }
        
        // Check if current nodes are equal without flipping
        if (flipEquiv(root1->left, root2->left) && flipEquiv(root1->right, root2->right)) {
            return true;
        }
        
        // Check if current nodes are equal after flipping
        if (flipEquiv(root1->left, root2->right) && flipEquiv(root1->right, root2->left)) {
            return true;
        }
        
        return false;
    }
};

Time Complexity: O(min(N1, N2))

Where N1 and N2 are the number of nodes in the two trees. We visit each node at most once.

Space Complexity: O(min(H1, H2))

Where H1 and H2 are the heights of the two trees. The recursion stack can go as deep as the height of the smaller tree.

JavaScript Solution

/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {boolean}
 */
var flipEquiv = function(root1, root2) {
    if (!root1 && !root2) {
        return true;
    }
    if (!root1 || !root2 || root1.val !== root2.val) {
        return false;
    }
    
    // Check if current nodes are equal without flipping
    if (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right)) {
        return true;
    }
    
    // Check if current nodes are equal after flipping
    if (flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left)) {
        return true;
    }
    
    return false;
};

Time Complexity: O(min(N1, N2))

Where N1 and N2 are the number of nodes in the two trees. We visit each node at most once.

Space Complexity: O(min(H1, H2))

Where H1 and H2 are the heights of the two trees. The recursion stack can go as deep as the height of the smaller tree.

C# Solution

public class Solution {
    public bool FlipEquiv(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return true;
        }
        if (root1 == null || root2 == null || root1.val != root2.val) {
            return false;
        }
        
        // Check if current nodes are equal without flipping
        if (FlipEquiv(root1.left, root2.left) && FlipEquiv(root1.right, root2.right)) {
            return true;
        }
        
        // Check if current nodes are equal after flipping
        if (FlipEquiv(root1.left, root2.right) && FlipEquiv(root1.right, root2.left)) {
            return true;
        }
        
        return false;
    }
}

Time Complexity: O(min(N1, N2))

Where N1 and N2 are the number of nodes in the two trees. We visit each node at most once.

Space Complexity: O(min(H1, H2))

Where H1 and H2 are the heights of the two trees. The recursion stack can go as deep as the height of the smaller tree.