Question

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.

Difficulty:Medium

Category:Tree

Analyze

Solution

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
// Runtime: 4ms
class Solution {
 public:
  bool flipEquiv(TreeNode* root1, TreeNode* root2) {
    if (!root1 && !root2) return true;
    if (!root1 || !root2) return false;
    bool l1 = flipEquiv(root1->left, root2->right);
    bool l2 = flipEquiv(root1->left, root2->left);
    bool r1 = flipEquiv(root1->right, root2->left);
    bool r2 = flipEquiv(root1->right, root2->right);

    return root1->val == root2->val && (l1 && r1) || (l2 && r2);
  }
};