021.二叉树匹配问题续

对称二叉树

题目链接

leetcode 101

题意

给你一个二叉树的根节点 root ， 检查它是否轴对称

思路

判断两颗树是否相等，我们递归检查它们的左子树，右子树是否对应相等

    bool isSameTree(TreeNode* p, TreeNode* q) {if(p==nullptr&&q==nullptr)return 1;if(p==nullptr||q==nullptr)return 0;if(p->val!=q->val)return 0;return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);}

现在要判断是否对称

我们只需交叉判断左右子树即可

    bool isSymmetric(TreeNode* root) {return dfs(root->left,root->right);}bool dfs(TreeNode*l,TreeNode*r){if(l==nullptr&&r==nullptr)return 1;if(l==nullptr||r==nullptr)return 0;if(l->val!=r->val)return 0;return dfs(l->right,r->left)&&dfs(l->left,r->right);//交叉}

翻转等价二叉树

题目链接

leetcode 951

题意

我们可以为二叉树 T 定义一个 翻转操作 ：

选择任意节点，然后交换它的左子树和右子树

只要经过一定次数的翻转操作后，能使 X 等于 Y，我们就称二叉树 X 翻转 等价 于二叉树 Y。

判断两棵树是否翻转等价

思路

暴力穷举在每个点处是否翻转

也就是同时判断 翻转 和 不翻转 两种情况，任一匹配即可

    bool flipEquiv(TreeNode* root1, TreeNode* root2) {if(root1==nullptr&&root2==nullptr)return 1;if(root1==nullptr||root2==nullptr)return 0;if(root1->val!=root2->val)return 0;return (flipEquiv(root1->left,root2->right)&&flipEquiv(root1->right,root2->left))||(flipEquiv(root1->left,root2->left)&&flipEquiv(root1->right,root2->right));}