《每日一套题·提升你我能力》· 第五篇

大家好，我是安然无虞。

文章目录

每篇前言

博客主页：安然无虞

作者认证：2021年博客新星Top2

咱的口号：🌹小比特，大梦想🌹

作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请铁汁批评斧正。

火爆专栏：蓝桥杯基础算法剖析
欢迎加入：比特社区

种一棵树最好的时间是十年前，其次是现在。

各位，共勉。

一、选择填空题

知识点补充

I.满二叉树和完全二叉树：

• 一个二叉树， 如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说， 如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树；

• 对于深度为K且有 n 个结点的二叉树， 当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树 。 要注意的是满二叉树是一种特殊的完全二叉树。（可能这样叙述并不是很清楚，没关系，请看下面）

看过来：
II.二叉树性质：

• 若规定根节点的层数是1，则一颗非空二叉树的第i层最多有2^(i-1) 个节点；
• 如规定根节点的层数是1，则深度为h的二叉树的最大节点数是2^h - 1，对，属于满二叉树；
• 对于任何一棵二叉树来说，如果度为0的叶节点个数是N0，度为2的节点个数是N2，那么总有N0 = N2 + 1;
• 若规定根节点的层数是1，具有n个节点的满二叉树的深度是h = log(N+1)。

1.题目一：考察性质

1.某二叉树共有399个节点，其中199个是度为2的节点，则该二叉树的叶子节点是：___ 个

本题主要考查性质三，X0 = X2 + 1，所以X0 = 200，即叶子结点个数为200个，这道题目知道性质3就很简单了。

2.题目二：考察性质

2.在具有2n 个节点的完全二叉树中，叶子结点个数为：___ 个。

需要注意的是，对于完全二叉树来说，度为1的结点个数只可能有0个或者1个。

3.题目三：考察性质

一颗完全二叉树的节点个数为531个，那么这棵树的高度为()
A:11
B:10
C:8
D:12

方法1

方法2

代入之后很明显，答案选择B

4.题目四：考察性质

一个具有767个节点的完全二叉树，其叶子结点个数为()
A:383
B:384
C:385
D:386
这道题跟第二题很相似，所以能看出什么，性质很重要，需要记住哦。

二、编程设计题

面试题：反转链表

原题链接：反转链表
题目描述：
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例：

解题思路1：翻指针方向

不过直接翻指针方向这个方法定义两个指针是翻不动的，需要定义三个指针，可能看下图很难理解，但是要结合代码去理解，最好自己能画一遍，尝试自己写一遍代码。初始代码：

struct ListNode*reverseList(struct ListNode* head){//判断特殊情况if(head ==NULL)returnNULL;struct ListNode* n1 =NULL,*n2 = head,*n3 = n2->next;while(n2){
       n2->next = n1;
       n1 = n2;
       n2 = n3;//注意哦，当n3指向空指针时再执行n3 = n3->next;会导致空指针异常if(n3)
           n3 = n3->next;}return n1;}

完整代码：
优化后的代码：

struct ListNode*reverseList(struct ListNode* head){struct ListNode* n1 =NULL,*n2 = head;while(n2){struct ListNode* n3 = n2->next;
       n2->next = n1;
       n1 = n2;
       n2 = n3;}return n1;}

是不是变得很简单，这样写也无需判断特殊情况。
完整代码：

解题思路2：头插法

之所以需要多定义一个指针，是因为要保证能找到下一个。
代码执行:

struct ListNode*reverseList(struct ListNode* head){struct ListNode* newHead =NULL;struct ListNode* cur = head;while(cur){//之所以将next定义在循环里是为了防止head为空时造成野指针struct ListNode* next = cur->next;
       cur->next = newHead;
       newHead = cur;
       cur = next;}return newHead;}

完整代码：

面试题：链表的中间节点

原题链接：链表的中间节点
题目描述：
给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
示例：

解题思路

本题比较简单，直接利用快慢指针即可但是有两点需要注意，会在下面给出
代码执行：

struct ListNode*middleNode(struct ListNode* head){struct ListNode* slow = head,*fast = head;//注意循环条件：想的是结束条件，写的是继续条件while(fast && fast->next){
       slow = slow->next;
       fast = fast->next->next;}return slow;}

完整代码：
试想：为什么循环条件不能写成fast->next && fast？
因为如果节点个数是偶数个，那么fast会走到最后一个节点的next位置，也就是NULL，此时再判断循环条件fast->next时会导致野指针。（可能这样叙述不好理解哦，没关系，动手画画图就很容易理解啦。）

面试题：回文链表

原题链接：回文链表
题目描述：
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。
示例：
1->2->2->1
返回：true

解题思路

之所以讲解前面两题，实际上都是为这道题准备的，本题的解题步骤是：

• 找出链表的中间位置；
• 逆置后半段
• 最后从头依次比较即可

代码执行：

//回文链表
class PalindromeList {
public://判断中间结点struct ListNode*middleNode(struct ListNode* A){struct ListNode* slow = A,*fast = A;while(fast && fast->next){
           slow = slow->next;
           fast = fast->next->next;}return slow;}//反转后半部分struct ListNode*reverseAfter(struct ListNode* mid){struct ListNode* newHead =NULL,*cur = mid;while(cur){struct ListNode* next = cur->next;
           cur->next = newHead;
           newHead = cur;
           cur = next;}return newHead;}
   bool chkPalindrome(ListNode* A){// write code here//先判断中间结点struct ListNode* mid =middleNode(A);//再反转后半部分struct ListNode* rHead =reverseAfter(mid);while(A && rHead){if(A->val != rHead->val){return false;}else{
               A = A->next;
               rHead = rHead->next;}}return true;}};

完整代码：

三、遇见安然遇见你，不负代码不负卿。

码字不易，求个三连

抱拳了兄弟们。