建站网站建设百家号自媒体平台注册
树的子结构
递归思维：对称性递归
什么是对称性递归？就是对一个对称的数据结构（这里指二叉树）从整体的对称性思考，把大问题分解成子问题进行递归，即不是单独考虑一部分(比如树的左子树)，而是同时考虑对称的两部分(左右子树)，从而写出对称性的递归代码。
题型分类：
可以用对称性递归解决的二叉树问题大多是判断性问题(bool类型函数),这一类问题又可以分为以下两类：
1、不需要构造辅助函数。这一类题目有两种情况：第一种是单树问题，且不需要用到子树的某一部分(比如根节点左子树的右子树)，只要利用根节点左右子树的对称性即可进行递归。第二种是双树问题，即本身题目要求比较两棵树，那么不需要构造新函数。
2、需要构造辅助函数。这类题目通常只用根节点子树对称性无法完全解决问题，必须要用到子树的某一部分进行递归，即要调用辅助函数比较两个部分子树。形式上主函数参数列表只有一个根节点，辅助函数参数列表有两个节点。
思路：
此题与572. 另一棵树的子树非常相似，但判断方式不一样。
子结构要么是它本身，要么在它的左子树里面，要么在它的右子树里面。
a) 所以在isSubStructure函数里面要判断是A自身，还是A的左边或右边与B对应 ；
return compare(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
b) 每次如果匹配失败，必须让B从头开始匹配，而不是直接单层递归compare(A->left,B)||compare(A->right,B),因为此时的B可能是上一层递归传过来的B->next，并不是B真正的根节点；
在递归第一层的时候要检查B是否为空，如果刚开始B就是空树，那么肯定不是子结构；
compare函数里面需要判断：
a) 当B遍历完了，A也遍历完了或者B遍历完了，A还没遍历完，那么B就是子结构；
b) 当A遍历完了，B还没遍历完，说明B不是子结构；
c) 如果AB都没完，但是当前结点值不想等，那么肯定不是子结构；
d) 此时AB都没完，值也相等，那么接着在compare函数里面找AB对应的左右孩子是否相对应；
class Solution {
public:bool compare(TreeNode* A,TreeNode* B){//如果B遍历完，A还没遍历完，那么B是子结构，或者A和B都正好遍历完（前提是遍历过程中都匹配上）if(B==NULL) return true;//如果A遍历完，B还没完，那么B不是子结构if(A==NULL) return false;//如果两个都不空，节点值不同，那么不是子结构if(A->val!=B->val) return false;//如果现在节点值和子树节点值相同，再分别检查两个的左右孩子return compare(A->left,B->left)&&compare(A->right,B->right);}bool isSubStructure(TreeNode* A, TreeNode* B) {if(B==NULL) return false;if(A==NULL) return false;//要么本身比较，要么是它的左子树，要么是右子树return compare(A,B)||isSubStructure(A->left,B)||isSubStructure(A->right,B);}
};2.二叉树的镜像（翻转二叉树）
将二叉树的左右孩子交换即可
class Solution {
public:TreeNode* mirrorTree(TreeNode* root) {if(root==NULL) return NULL;swap(root->left,root->right);mirrorTree(root->left);mirrorTree(root->right);return root;}
};3.对称的二叉树
其实我们要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。
class Solution {
public:bool compare(TreeNode* left,TreeNode* right){//首先排除空节点情况if(left==NULL&&right==NULL) return true;else if(left!=NULL&&right==NULL) return false;else if(left==NULL&&right!=NULL) return false;//排除值不同的情况else if(left->val!=right->val) return false;//此时左右节点的数值相同,这时再往下做递归//对于左子树而言 左右中 //对于右子树而言 右左中bool outside=compare(left->left,right->right);bool inside=compare(left->right,right->left);return outside&&inside;}bool isSymmetric(TreeNode* root) {if(root==NULL) return true;return compare(root->left,root->right);}
};