泵网站建设,衡阳网页定制,网站建设互联网营销营销推广,服装网站源码php目录
选择题#xff1a;
题一#xff1a;
题二#xff1a;
题三#xff1a;
题四#xff1a;
题五#xff1a;
编程题#xff1a;
题一#xff1a;单值二叉树
思路一#xff1a;
题二#xff1a;二叉树的最大深度
思路一#xff1a;
本人实力有限可能对…
目录
选择题
题一
题二
题三
题四
题五
编程题
题一单值二叉树
思路一
题二二叉树的最大深度
思路一
本人实力有限可能对一些地方解释和理解的不够清晰可以自己尝试读代码或者评论区指出错误望海涵
感谢大佬们的一键三连 感谢大佬们的一键三连 感谢大佬们的一键三连 选择题
题一 1.一颗拥有1000个结点的树度为4则它的最小深度是( ) A.5 B.6 C.7 D.8 答案解析 如果这棵树每一层都是满的则它的深度最小假设它为一个四叉树高度为h则这个数的节点个数为(4^h - 1) / 3当h 5, 最大节点数为341 当h 6, 最大节点数为1365所以最小深度应该为6。 题二 2.设一棵二叉树中有3个叶子结点有8个度为1的结点则该二叉树中总的结点数为( )个 A.11 B.12 C.13 D.14 答案解析 设Ni表示度为i的节点个数则节点总数 N N0 N1 N2 节点个数于节点边的关系 N个节点的树有N-1个边 边与度的关系N - 1 N1 2 * N2 故N0 N1 N2 - 1 N1 2 * N2 因此得N0 N2 1 回到原题N0 3N1 8可得N2 2。 因此答案是 3 8 2 13。 题三 3.在一颗度为3的树中度为3的结点有2个度为2的结点有1个度为1的结点有2个则叶子结点有( )个 A.4 B.5 C.6 D.7 答案解析 设度为i的节点个数为ni, 该树总共有n个节点,则nn0n1n2n3. 有n个节点的树的总边数为n-1条. 根据度的定义,总边数与度之间的关系为n-10*n01*n12*n23*n3. 联立两个方程求解,可以得到n0 n2 2n3 1, n06 题四 4.下列关于二叉树的叙述错误的是( ) A.二叉树指的是深度为 2 的树 B.一个 n 个结点的二叉树将拥有 n-1 条边 C.一颗深度为 h 的满二叉树拥有 2^h-1 个结点根结点深度为1 D.二叉树有二叉链和三叉链两种表示方式 答案解析 A错误: 二叉树指最大孩子个数为2即树的度为二的树。深度描述的为树的层数。 B正确: 对于任意的树都满足边的条数比节点个数少1因为每个节点都有双亲但是根节点没有 C正确: 正确参加二叉树性质 D正确: 二叉链一般指孩子表示法三叉连指孩子双亲表示法这两种方式是二叉树最常见的表示方式虽然还有孩子兄弟表示法该中表示方式本质也是二叉链 题五 5.下列关于堆的叙述错误的是 A.堆是一种完全二叉树 B.堆通常使用顺序表存储 C.小堆指的是左右孩子结点都比根结点小的堆 D.堆的删除是将尾部结点放到队顶后执行向下调整算法 答案解析 堆是在完全二叉树的基础上进行了条件的限制即每个节点都比其孩子节点大则为大堆每个节点都比其孩子节点小则为小堆完全二叉树比较适合使用顺序结构存储。 堆删除删的是堆顶元素常见操作是将堆顶元素与堆中最后一个元素交换然后对中元素个数减少一个重新将堆顶元素往下调整故C错误 编程题
题一单值二叉树
965. 单值二叉树 - 力扣LeetCode 思路一 对整棵二叉树进行遍历比较 第一步优先判断树是否为空空树为真 第二步判断左树是否存在且左树值等于根值然后再判断右树存在且右树值等于根值; 第三步最后,以当前为节点遍历左子树和右子树。
bool isUnivalTree(struct TreeNode* root)
{//判断子树是否为空if(root NULL)return true;//左树存在且左树值等于根值if(root-left root-left-val ! root-val)return false;//右树存在且右树值等于根值if(root-right root-right-val ! root-val)return false;//递归判断子树值是否都相等return isUnivalTree(root-left) isUnivalTree(root-right);
}
题二二叉树的最大深度
104. 二叉树的最大深度 - 力扣LeetCode 思路一 第一步判断树是否为空为空返回0 第二步定义一个leftdeep记录除根层以外左子树层数定义一个rightdeep记录除根层以右左子树层数 第三步当遍历到树的子节点 返回值最大的值1(加上当前层).
int maxDepth(struct TreeNode* root)
{ if(root NULL)return 0;//记录除根层以外左子树层数int leftdeep maxDepth(root-left);//记录除根层以外右子树层数int rightdeep maxDepth(root-right);return leftdeep rightdeep ? leftdeep1 : rightdeep1;
} 本人实力有限可能对一些地方解释和理解的不够清晰可以自己尝试读代码或者评论区指出错误望海涵
感谢大佬们的一键三连 感谢大佬们的一键三连 感谢大佬们的一键三连
