Flip Equivalent Binary Trees Problem


Description

LeetCode Problem 951.

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 Xis 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:

1
2
3
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:

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

Example 3:

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

Example 4:

1
2
Input: root1 = [0,null,1], root2 = []
Output: false

Example 5:

1
2
Input: root1 = [0,null,1], root2 = [0,1]
Output: true

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].


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool flipEquiv(TreeNode* root1, TreeNode* root2) {
        if (root1 == NULL and root2 == NULL)
            return true;
        if (root1 == NULL or root2 == NULL)
            return false;
        if (root1->val != root2->val)
            return false;
        
        bool non_flip = flipEquiv(root1->left, root2->left) && 
            flipEquiv(root1->right, root2->right);
        bool flip = flipEquiv(root1->left, root2->right) && 
            flipEquiv(root1->right, root2->left);
        
        return non_flip || flip;
    }
};




Related Posts

Vertical Order Traversal Of A Binary Tree Problem

LeetCode 987. Given the root of a binary tree, calculate...

Univalued Binary Tree Problem

LeetCode 965. A binary tree is uni-valued if every node...

Sum Of Distances In Tree Problem

LeetCode 834. There is an undirected connected tree with n...

Smallest Subtree With All The Deepest Nodes Problem

LeetCode 865. Given the root of a binary tree, the...

Smallest String Starting From Leaf Problem

LeetCode 988. You are given the root of a binary...

Similar String Groups Problem

LeetCode 839. Two strings Xand Yare similar if we can...