产品销售型的网站,wordpress 搜索出图片,抖音代运营正规公司,网站如何建设与安全♥♥♥~~~~~~欢迎光临知星小度博客空间~~~~~~♥♥♥ ♥♥♥零星地变得优秀~也能拼凑出星河~♥♥♥ ♥♥♥我们一起努力成为更好的自己~♥♥♥ ♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥ ♥♥♥如果有什么问题可以评论区留言或者私信我哦~♥♥♥ 知道了二叉树的结… ♥♥♥~~~~~~欢迎光临知星小度博客空间~~~~~~♥♥♥ ♥♥♥零星地变得优秀~也能拼凑出星河~♥♥♥ ♥♥♥我们一起努力成为更好的自己~♥♥♥ ♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥ ♥♥♥如果有什么问题可以评论区留言或者私信我哦~♥♥♥ 知道了二叉树的结构和一些基本操作~这一篇博客是一些关于二叉树的OJ练习题~
练习1单值二叉树
力扣——965单值二叉树
题目 题目中给出了单值二叉树的含义就是二叉树每一个结点保存的数据相等函数返回值是bool类型如果是单值二叉树就返回true否则返回false。同时题目也给出了它定义的二叉树 思路
既然这里涉及到保存数据的比较那么肯定需要遍历我们的二叉树了具体怎么比较呢我们给出思路~ 思路 让根结点分别与左右孩子结点孩子结点要不为空数据比较~如果不相等就返回false~这里根结点与左右孩子结点比较就不需要左右孩子结点之间进行比较了如果【根结点右孩子结点】【根结点右孩子结点】那么【左孩子结点右孩子结点】 处理特殊情况 如果根结点为空return true; 依次递归比较树的左右子树 代码 bool isUnivalTree(struct TreeNode* root) {if(root NULL){return true;}//根结点分别与不为空左右孩子结点数据比较//不相等返回falseif(root-left root-val ! root-left-val){return false;}if(root-right root-val ! root-right-val){return false;}//递归比较return (isUnivalTree(root-left))(isUnivalTree(root-right));
} 提交通过~再一次体会到了二叉树递归的魅力~
练习2相同的树
力扣——100相同的树
题目 这个题目希望我们判断两颗树是不是相同的二叉树相同也就是它们相对应的结点保存的数据相同~ 思路 思路 这个题同样是递归比较的方法比较两颗树相对应的结点是否相同如果不相同就返回false 处理特殊情况 如果两个结点都为空 return true; 如果只有一个结点为空 return false 依次递归比较两颗树的左右子树 代码 bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//两个结点都为空相同if(p NULL q NULL){return true;}//只有一个为空,不相同if(p NULL || q NULL){return false;}if(p-val ! q-val){return false;}//递归比较两颗树左右子树return isSameTree(p-left,q-left) isSameTree(p-right,q-right);
} 提交通过~
练习3另外一棵树的子树
力扣——另外一棵树的子树
题目 这里是不是就与上一个题目有相通的地方如果判断一个树是不是另外一棵树的子树我们是不是也就可以从根结点开始遍历另外一棵树与树进行比较判断是不是相同的树进而判断是不是子树
思路 从根结点root开始判断两颗树是不是相同的树如果不是将左右子树与subRoot进行判断是不是相同的树~ 注意 当根结点为NULL说明两棵树一定不是相同的树那么subRoot也就不是root的子树返回false。 代码
我们这里就可以直接把判断是不是相同的树的代码拿过来~
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//两个结点都为空相等if(p NULL q NULL){return true;}//只有一个为空,不相等if(p NULL || q NULL){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(root NULL){return false;}//两颗树相同是子树if(isSameTree(root , subRoot)){return true;}//递归遍历判断左右子树//只要有一个满足就是return (isSubtree(root-left,subRoot) || isSubtree(root-right,subRoot));
} 提交通过~
练习4对称二叉树
力扣——101对称二叉树
题目 这里需要我们判断是不是轴对称图形不是判断左右子树相同这个题应该怎么做呢
思路
有了前面两题的基础相信这一个题目也就是手到擒来~ 思路如果root为NULL直接返回true。接着我们只需要判断左右子树是不是对称的树这里的对称也就说明左子树的左结点保存的数据等于右子树的右结点保存的数据左子树的右结点保存的数据等于右子树的左结点保存的数据。 判断一个树是否对称首先要判断左右孩子是否对称相等还需要判断左孩子的左子树是否和右孩子的右子树对称左孩子的右子树是否和右孩子的左子树对称。 代码
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//两个结点都为空相同if(p NULL q NULL){return true;}//只有一个为空,不相同if(p NULL || q NULL){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) {if(root NULL){return true;}//比较左右子树if(isSameTree(root-left,root-right)){return true;}//else与最近的if搭配else{return false;}
} 提交通过~
今天的二叉树题目练习结束再一次体会到了递归的暴力美学~ ♥♥♥本篇博客内容结束期待与各位优秀程序员交流有什么问题请私信♥♥♥ ♥♥♥如果这一篇博客对你有帮助~别忘了点赞分享哦~♥♥♥
