Algorithm
Problem Name: 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.
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]
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
bool flipEquiv(TreeNode* root1, TreeNode* root2) {
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);
}
};
Input
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public boolean flipEquiv(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 == null) {
return true;
}
if (root1 == null || root2 == null) {
return false;
}
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)
)
);
}
}
Input
Output
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const flipEquiv = function(root1, root2) {
if(root1 == null || root2 == null) return root1 === root2
return root1.val === root2.val &&
(
(flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right)) ||
(flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left))
)
};
Input
Output
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def flipEquiv(self, root1, root2):
if not root1 or not root2: return root1 == root2
if root1.left and root2.left and root1.left.val != root2.left.val or (not root1.left and root2.left) or (root1.left and not root2.left):
root1.left, root1.right = root1.right, root1.left
return root1.val == root2.val and self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right)
Input
Output
#5 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0951_FlipEquivalentBinaryTrees
{
public bool FlipEquiv(TreeNode root1, TreeNode root2)
{
if (root1 == null) return root2 == null;
if (root2 == null) return root1 == null;
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));
}
}
}
Input
Output