东莞效果好的网站建设,wordpress支持建多个站点吗,如何建立免费微网站,wordpress在本地建站树的子结构递归思维#xff1a;对称性递归什么是对称性递归#xff1f;就是对一个对称的数据结构#xff08;这里指二叉树#xff09;从整体的对称性思考#xff0c;把大问题分解成子问题进行递归#xff0c;即不是单独考虑一部分(比如树的左子树)#xff0c;而是同时考…树的子结构递归思维对称性递归什么是对称性递归就是对一个对称的数据结构这里指二叉树从整体的对称性思考把大问题分解成子问题进行递归即不是单独考虑一部分(比如树的左子树)而是同时考虑对称的两部分(左右子树)从而写出对称性的递归代码。题型分类可以用对称性递归解决的二叉树问题大多是判断性问题(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(BNULL) return true;//如果A遍历完B还没完那么B不是子结构if(ANULL) 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(BNULL) return false;if(ANULL) return false;//要么本身比较要么是它的左子树要么是右子树return compare(A,B)||isSubStructure(A-left,B)||isSubStructure(A-right,B);}
};2.二叉树的镜像翻转二叉树将二叉树的左右孩子交换即可class Solution {
public:TreeNode* mirrorTree(TreeNode* root) {if(rootNULL) 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(leftNULLrightNULL) return true;else if(left!NULLrightNULL) return false;else if(leftNULLright!NULL) return false;//排除值不同的情况else if(left-val!right-val) return false;//此时左右节点的数值相同,这时再往下做递归//对于左子树而言 左右中 //对于右子树而言 右左中bool outsidecompare(left-left,right-right);bool insidecompare(left-right,right-left);return outsideinside;}bool isSymmetric(TreeNode* root) {if(rootNULL) return true;return compare(root-left,root-right);}
};
