大家好，我是安然无虞。

每篇前言

博客主页：安然无虞

作者认证：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)
       return NULL;
   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;
}

   

  

   
1
   
2
   
3
   
4
   
5
   
6
   
7
   
8
   
9
   
10
   
11
   
12
   
13
   
14
   
15
   
16
   
17
  

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

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;
}

   

  

   
1
   
2
   
3
   
4
   
5
   
6
   
7
   
8
   
9
   
10
   
11
   
12
  

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

解题思路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;
}

   

  

   
1
   
2
   
3
   
4
   
5
   
6
   
7
   
8
   
9
   
10
   
11
   
12
   
13
   
14
  

完整代码：

面试题：链表的中间节点

原题链接：链表的中间节点
题目描述：
给定一个头结点为 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;
}

   

  

   
1
   
2
   
3
   
4
   
5
   
6
   
7
   
8
   
9
   
10
   
11
  

完整代码：
试想：为什么循环条件不能写成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;
   }
};

   

  

   
1
   
2
   
3
   
4
   
5
   
6
   
7
   
8
   
9
   
10
   
11
   
12
   
13
   
14
   
15
   
16
   
17
   
18
   
19
   
20
   
21
   
22
   
23
   
24
   
25
   
26
   
27
   
28
   
29
   
30
   
31
   
32
   
33
   
34
   
35
   
36
   
37
   
38
   
39
   
40
   
41
   
42
   
43
   
44
   
45
   
46
   
47
   
48
   
49
  

完整代码：

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

码字不易，求个三连 抱拳了兄弟们。

文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。

原文链接：bit-runout.blog.csdn.net/article/details/123908553