免费做网站空间,wordpress百度云盘,wordpress 发布文章sql,如何做设计师个人网站主页点击直达#xff1a;个人主页
我的小仓库#xff1a;代码仓库
C语言偷着笑#xff1a;C语言专栏
数据结构挨打小记#xff1a;初阶数据结构专栏
Linux被操作记#xff1a;Linux专栏
LeetCode刷题掉发记#xff1a;LeetCode刷题
算法头疼记#xff1a;算法专栏…
主页点击直达个人主页
我的小仓库代码仓库
C语言偷着笑C语言专栏
数据结构挨打小记初阶数据结构专栏
Linux被操作记Linux专栏
LeetCode刷题掉发记LeetCode刷题
算法头疼记算法专栏 目录
前言
LeetCode 965.单值二叉树
LeetCode 100.相同的树
LeetCode 101.对称二叉树
LeetCode 144 145 94 .二叉树的前、中、后序遍历
LeetCode 572.另一棵树的子树 前言
在之前的文章讲解了二叉树的链式结构的实现以及前、中、后序的遍历。不知道大家看完后有没有理解和有所收获今天基于那篇文章给大家分享讲解几道经典的题目更便于大家的理解和深入。
二叉树的题目一定要会两个思想
第一个思想拆分 一定要将二叉树拆分为根、左子树、右子树首先就是要判断根结点是否为空。第二个思想递归善于使用递归。 LeetCode 965.单值二叉树
OJ链接 题目描述 如果二叉树每个节点都具有相同的值那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时才返回 true否则返回 false。 示例 1 输入[1,1,1,1,1,null,1]
输出true 示例 2 输入[2,2,2,5,2]
输出false审题总结 判断一个二叉树这所有节点的值是否相等相等返回true否则返回false 思路讲解首先判断根是否为空如果为空直接返回true。不为空判断左子树是否存在存在的话判断和根节点的值是否相等如果相等返回true否则返回false继续判断右子树是否存在存在的话判断和根节点的值是否相等如果相等返回true否则返回法false。左右子树都存在的话使用递归遍历。 接口代码 bool isUnivalTree(struct TreeNode* root){if(rootNULL)return true;if(root-leftroot-val!root-left-val)return false;if(root-rightroot-val!root-right-val)return false;return isUnivalTree(root-left)isUnivalTree(root-right);
} LeetCode 100.相同的树
OJ链接 题目描述给你两棵二叉树的根节点 p 和 q 编写一个函数来检验这两棵树是否相同 如果两个树在结构上相同并且节点具有相同的值则认为它们是相同的。 示例 1 输入p [1,2,3], q [1,2,3]
输出true 示例 2 输入p [1,2], q [1,null,2]
输出false示例 3 输入p [1,2,1], q [1,1,2]
输出false 思路讲解 先将根拆结点拆分出来两个根节点有三种情况都为空、两个根节点中有一个为空。如果都为空则返回true如果有一个为空则返回false。根节点判断完成后判断根节点的值是否相等使用递归遍历左子树和右子树。 接口代码 bool isSameTree(struct TreeNode* p, struct TreeNode* q){if(pNULLqNULL)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);
} LeetCode 101.对称二叉树
OJ链接 题目描述 给你一个二叉树的根节点 root 检查它是否轴对称。 示例 1 输入root [1,2,2,3,4,4,3]
输出true示例 2 输入root [1,2,2,null,3,null,3]
输出falses 思路讲解 这个题目和上个题目非常的相似还是拆分为根、左子树、右子树。这里将两个子树看成单独的树就和上面题的思路大差不差了。不同的是要判断左边的值和右边的值是否相等这样才算对称。 实现代码 bool isSameTree(struct TreeNode*p,struct TreeNode*q){if(pNULLqNULL){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){if(root!NULL){return isSameTree(root-left,root-right);}elsereturn true;
} LeetCode 144 145 94 .二叉树的前、中、后序遍历
前序遍历OJ链接
中序遍历OJ链接
后序遍历OJ链接 关于二叉树的前、中、后序遍历的文章点击直达这里我不做介绍。由于这三个题目是差不多只是将遍历的值用数组的形式便是出来所以我就只讲解前序遍历、中、后序遍历交给大家练习。 题目描述给你一棵二叉树的根节点 root 返回其节点值的 后序遍历 。 示例 1 输入root [1,null,2,3]
输出[3,2,1]示例 2 输入root []
输出[]示例 3 输入root [1]
输出[1]思路讲解 首先求出这棵二叉树有几个结点根据结点动态开辟相应大小的空间。将根节点、动态开辟的数组变量的地址交给一个前序遍历的函数根据前序遍历的规则进行递归给数组赋值。 实现代码 int treesize(struct TreeNode*root){return rootNULL? 0:treesize(root-left)treesize(root-right)1;}void preoder(struct TreeNode *root,int *a,int *pi){if(rootNULL)return;a[(*pi)]root-val;preoder(root-left,a,pi);preoder(root-right,a,pi);}
int* preorderTraversal(struct TreeNode* root, int* returnSize){int ntreesize(root);int *a(int *)malloc(sizeof(int )*n);int j0;preoder(root,a,j);*returnSizen;return a;
} LeetCode 572.另一棵树的子树
OJ链接 题目描述 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在返回 true 否则返回 false 。二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。 示例 1 输入root [3,4,5,1,2], subRoot [4,1,2]
输出true示例 2 输入root [3,4,5,1,2,null,null,null,null,0], subRoot [4,1,2]
输出falses 思路讲解 这个题和上面的LeetCode 100.相同的树基本上也大差不差。首先判断根节点是否为空如果根节点为空则直接返回false不为空则直接使用是否为相同的树判断函数判断所给树是否为子树如果为真则直接返回true使用递归遍历根节点的左右子树和所给所给子树相比较。 实现代码 bool isSameTree(struct TreeNode* p, struct TreeNode* q){if(pNULLqNULL)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(root-valsubRoot-val)
{if(isSameTree(root,subRoot))return true;
}
return isSubtree(root-left,subRoot)||isSubtree(root-right,subRoot);} 今天的分享就到此结束了希望大家阅读完可以有所收获同时也感谢各位看官的三连支持。文章有问题可以直接留言我一定及时认真的修改。
