判断两棵二叉树是否等价：若两棵二叉树可以通过任意次的交换任意节点的左右子树变为相同，则称两棵二叉树等价。

 

思路：遍历二叉树，判断所有的子树是否等价。

struct TreeNode{    int val;    TreeNode *left;    TreeNode *right;    TreeNode(int x)        : val(x), left(NULL), right(NULL) {}};class Solution{public:    void exchangeSons(TreeNode* root)    {        TreeNode* tmp = root->left;        root->left = root->right;        root->right = tmp;    }    int getNum(TreeNode* node)    {        if(node == NULL)            return -1;        else            return node->val;    }    int compareSons(TreeNode* root1, TreeNode* root2)    {        TreeNode* left1 = root1->left;        TreeNode* right1 = root1->right;        TreeNode* left2 = root2->left;        TreeNode* right2 = root2->right;        int l1,l2,r1,r2;        l1 = getNum(left1);        l2 = getNum(left2);        r1 = getNum(right1);        r2 = getNum(right2);        if(l1 == l2 && r1 == r2)            return 1;        else if(l1 == r2 && r1 == l2)            return 2;        else            return 0;    }    bool flipEquiv(TreeNode* root1, TreeNode* root2)    {        if(root1 == NULL && root2 == NULL)            return 1;        else if(root1 == NULL)            return 0;        else if(root2 == NULL)            return 0;        int comres = compareSons(root1, root2);        if(comres == 0)            return 0;        else if(comres == 2)            exchangeSons(root2);        bool leftEquiv = 1,rightEquiv = 1;        if(root1->left != NULL)            leftEquiv = flipEquiv(root1->left, root2->left);        if(root1->right != NULL)            rightEquiv = flipEquiv(root1->right, root2->right);        if(leftEquiv&&rightEquiv)            return 1;        else            return 0;    }};

 

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.

 

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: trueExplanation: We flipped at nodes with values 1, 3, and 5.

 

Note:

1. Each tree will have at most 100 nodes.
2. Each value in each tree will be a unique integer in the range [0, 99].