手机网站建设哪里好,长春建设股份有限公司,wordpress安装主题后打不开后台,全国软件公司排名目录
一#xff0c;对称二叉树
题目详情#xff1a;
解题思路#xff1a;
思路实现#xff1a;
源代码#xff1a;
二#xff0c;另一颗树的子树
题目详情#xff1a;
解题思路#xff1a;
思路实现#xff1a;
源代码#xff1a; 前言#xff1a; 接下来… 目录
一对称二叉树
题目详情
解题思路
思路实现
源代码
二另一颗树的子树
题目详情
解题思路
思路实现
源代码 前言 接下来呢也还是带大家继续刷题二叉树这个部分涉及较多的递归而递归又是一个很繁琐的过程所以我们需要大量的练习来熟悉递归的过程 一对称二叉树
题目详情 给你一个二叉树的根节点 root 检查它是否轴对称 我们先来看几个例子然后再加以分析
示例1 输入root [ 1223443 ] 输出true 示例2 输入root [ 12233 ] 输出false 提示
树中结点数目在范围【11000】内
-100Node.val100 解题思路
从以上信息得知咱们就是要判断一个二叉树是否轴对称嘛是就返回 true 否就返回 false
开始分析
要判断一颗树是否轴对称根结点只有一个不用管但是根结点的左右子树要对称也就是相同
大事化小树要对称则根结点的左右子树也要对称也就是相同当左右子树为根结点时也是如此层层递归下去最后这棵树就成对称树了
结束条件当左右子树不相同时就结束所以当左右子树一方为 NULL另一方不为 NULL 时返回 false 当左右子树对应的值不相同时返回 false 当上面条件都满足时就要向下走了判断下层的结点也是否对称 思路实现
判断树是否对称侧重点在于根结点的左右子树是否相同所以我们需要编写一个函数来判断其左右子树是否相同
bool isSymmetric(struct TreeNode* root){//判断两棵树是否相同return isSameTree(root-left,root-right);
}
而 isSamTree 函数的实现类似于 相同的树 这道题目的解法前者是判断其左右子树是否相同后者是判断其左左子树右右子树是否相同有异曲同工之妙
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{//判空if(pNULL qNULL){return true;}if(pNULL || qNULL) {return false;}//判值if(p-val ! q-val){return false;}//递归return isSameTree(p-left,q-right) isSameTree(p-right,q-left);
} 源代码
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{//判空if(pNULL qNULL){return true;}if(pNULL || qNULL) {return false;}//判值if(p-val ! q-val){return false;}//递归return isSameTree(p-left,q-right) isSameTree(p-right,q-left);
}bool isSymmetric(struct TreeNode* root){//判断两棵树是否相同return isSameTree(root-left,root-right);
}二另一颗树的子树
题目详情 给你两棵二叉树 root 和 subRoot 检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在返回 true否则返回 false 二叉树 true的一棵子树包括 tree 的某个节点和这个节点的所有后代节点 tree 也可以看做它自身的一棵子树 我们先来看几个例子然后再加以分析
示例1 输入root [ 34512 ]subRoot [ 412 ] 输出true 示例2 输入root [ 34512nullnullnull0 ]subRoot [ 412 ] 输出false 提示
root 树上的结点数量范围是【12000】
subRoot 树上的结点数量范围是【11000】
-104 root.val 104
-104 subRoot.val 104 解题思路
其实这个题目讲的就是 root 树是否包含 subRoot 树嘛
开始分析要判断 root 为根结点的树是否包含以 subRoot 为结点的树就要看自身有没有子树与 subRoot 树相同
大事化小先判断树的根结点是否与 subRoot 树相等否则再判断其左右子树是否与 subRoot 树相等层层递归下去进行判断只要左右子树中有一方与 subRoot 树相等则 root 树包含 subRoot 树
结束条件因为 subRoot 树上的结点至少都为1所以当 root 树上的结点为空是返回 false 如果其子树与 subRoot 树相同返回 true 思路实现
首先是对结点进行判空 //判空if(rootNULL){return false;}
然后在判断以此结点为根结点的树是否与 subRoot 树相同 bool isSameTree(struct TreeNode* p, struct TreeNode* q){if(pNULL qNULL){return true;}if(pNULL || qNULL) {return false;}if(p-val ! q-val){return false;}return isSameTree(p-left,q-left) isSameTree(p-right,q-right);
} //判断树是否相同if(isSameTree(root,subRoot)){return true;}
root 树中的左右子树中只要有一方包含 subRoot 树直接为真 //判断其子树是否包含 subRoot 树return isSubtree(root-left,subRoot) || isSubtree(root-right,subRoot); 源代码
bool isSameTree(struct TreeNode* p, struct TreeNode* q){if(pNULL qNULL){return true;}if(pNULL || qNULL) {return false;}if(p-val ! q-val){return false;}return isSameTree(p-left,q-left) isSameTree(p-right,q-right);
}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){//判空if(rootNULL){return false;}//判断树是否相同if(isSameTree(root,subRoot)){return true;}//判断其子树是否包含 subRoot 树return isSubtree(root-left,subRoot) || isSubtree(root-right,subRoot);
}
这两道题目都跟前面的题目有所关联互相的联系也多也都是用递归来实现的总体来说不算难可以好好熟悉一下递归
第六阶段就到这里了这阶段带大家继续刷题来熟悉递归解题思路
后面博主会陆续更新
如有不足之处欢迎来补充交流
完结。。
