方法一：递归

树的题，大部分都是递归。这道题的话，和same tree很像，无非就是加个判断看看是不是翻转的。

时间复杂度：T(n) = 4T(n/2), by Master Theorem, 时间复杂度 O(n^2)

空间复杂度：O(h)

class Solution {public:    bool flipEquiv(TreeNode* root1, TreeNode* root2) {        if (root1==NULL && root2==NULL) return true;        if (root1==NULL || root2==NULL) return false;                // here root1 not null, root2 not 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);    }};

 

方法二：Serialize Tree

Serialize Tree方法很多，可以参考那一道题。这里就用preorder。

考虑到翻转，所以序列化的时候，dfs的时候，左右儿子中val小的先遍历，这样就算有翻转的情况，最后serialize的结果也是一样的。

class Solution {public:    bool flipEquiv(TreeNode* root1, TreeNode* root2) {        return serialize(root1)==serialize(root2);    }        string serialize(TreeNode *root){        if (root==NULL) return "#";                string res=to_string(root->val);        int left_val=root->left!=NULL?root->left->val:-1;        int right_val=root->right!=NULL?root->right->val:-1;        if (left_val
     
      left) + ' ' + serialize(root->right);        else            res += ' ' + serialize(root->right) + ' ' + serialize(root->left);        return res;     }};
     

时间复杂度：和遍历树类似，O(n)

空间复杂度：serialize后字符串需要占空间。