😎感受递归分治的魅力吧！

本章节一共可以实现下面几个功能函数：
求
Size 二叉树节点个数、
Height 树的高度、
KNum 第k层节点个数、
Find 查找节点、
Leaves 叶子节点个数、
Destroy 销毁

前言：本章节函数的实现有些会借助到 前序遍历、层序遍历…等函数
这些函数 在 【二叉树】第一章：相关性质与四种遍历 有讲解
可以先把 第一章内容先学习完

---

---

正文

😀 递归分治 思想 与 应用：二叉树相关函数的实现

分治分治，分而治之：将大问题分解成同类型的小问题，解决小问题后，大问题也就解决了

此谓之，递归分治之精髓

遇到需要递归的题目，直接想 递归分治两部曲，这部分看不懂，记住递归分治两部曲，多看章节下部分的多个函数的实现应用，就可以逐步明白理解

递归分治两部曲

1.子问题是什么：不要想其他步骤怎么来的，你就想你当前的子问题 怎么得出来的

2.返回条件是什么（最小子问题 或 递归出口）：即最小的子问题到哪结束

同时，在 二叉树章节，递归分治问题中，NULL 都肯定可以算作一个最小子问题，但是往往最小子问题不唯一

⭐例如：算二叉树的 高度

前言：因为二叉树的高度取决于 自己下面的 子树最多可以延伸多少层，所以求 cnt 的最大值

1.子问题：当前节点的 最大高度为：$1+max(Height(root->Left),Height(root->Right))$ : 即当前这层也算一层，加上左右子树的 高度最高的那个

至于左右子树的高度(Height(root->Left), Height(root->Right) 怎么算出来的不要管，你明白子问题是什么，单独处理子问题就行

2.返回条件是什么：当遍历到 叶子节点，已经没有左右子树了，此时已经结束延伸了，可以 return 结束了： $if(root==NULL)$

---

---

一、Size 计算节点总数

递推分治法

1.子问题是什么：

每一个节点代表 以 该节点 为根的子树 的节点个数

每个根节点的节点个数来源有两方面：左子树 和 右子树

return 1 + Size(root->Left) + Size(root->Right);

1 表示 当前这个根节点自己算作一个

Size(root->Left) + Size(root->Right) ：表示 左子树节点总数 和 右子树节点总数

2.返回条件是什么

分解成最小子问题：当前根节点的 左右子树都是 NULL，即到叶子节点了 ： return 1 + 0 + 0；

这样就收集到了一个节点：return 1;

依次类推，宏观的从叶子节点向上推到累加，最终大树的根节点就是 全部节点的总数了

// 方法：递归分治
// 每个根节点所代表的节点总数 = 1 + 左子树节点个数 + 右子树节点个数
int Size(BTNode* root)
{if (root == NULL) { // 到 NULL return 0 : NULL 这个子树的节点个数 肯定是 0 呀return 0;}return 1 + Size(root->Left) + Size(root->Right);
}

---

---

二、Height 算二叉树的 高度

因为二叉树的高度取决于 自己下面的 子树最多可以延伸多少层

因此 我们求 二叉树的高度就是 求从根节点走到叶子节点 的最长路径

方法一、回溯法：

注意两种特例

测试用例一：root = [0] 输出：1

测试用例二：root = [] 输出：0

叶子节点作为最小子问题：容易 非法访问

若下面以 叶子节点 作为最小子问题递归出口（ if (root->left == NULL && root->right == NULL)），则这里必须加上 这句话（if (root == NULL) return 0; ），否则 比如 当前遍历到 2 的右节点，是 root == NULL，但是下面的 判断叶子节点的语句就会出现非法访问：NULL 是没有左右节点 的，不能 root->Left 和 root->Right 这样访问

回溯法思路：cnt 逐步记录层数，当遍历到 叶子节点，就记录当前 层数（ans 记录 最大的 cnt）

// cnt 是当前的层数：因为从根节点开始，初始化为 第一层
// ans 是最长的 cnt
int ans = -1, cnt = 1;  
int maxDepth(struct TreeNode* root) {if (root == NULL)  //  遇到 root == NULL 必须返回，若不返回，会进入到下面 判断 root->left 或 root->Right, NULL 本身 是没有左右节点 的，会造成 非法访问 的错误return 0;if (root->left == NULL && root->right == NULL) {   // 当遍历到 叶子节点，就记录当前 层数（ans 记录 最大的 cnt）ans = max(ans, cnt);return 1;}cnt++;  // 进入下一层：层数就 + 1maxDepth(root->left);cnt--;  // 递归退回来了：代表回到上一层了，层数 - 1cnt++;maxDepth(root->right);cnt--;return ans;
}

---

方法二、递归分治

递归分治两部曲：1.子问题；2.返回条件

1.子问题：当前节点的 最大高度为：$1+max(Height(root->Left),Height(root->Right))$ : 即当前这层也算一层，加上左右子树的 高度最高的那个

至于左右子树的高度怎么算出来的不要管，你明白子问题是什么，单独处理子问题就行

2.返回条件是什么：当遍历到 叶子节点，已经没有左右子树了，此时已经结束延伸了，可以 return 结束了： $if(root==NULL)$

// 因为上面的 回溯法 以叶子节点作为 最小子问题会  非法访问，下面方法直接就 以 NULL 为最小子问题
int Height(BTNode* root)
{if (root == NULL) {return 0;}return 1 + max(Height(root->Left), Height(root->Right));
}

---

---

三、KNum 计算第 k 层有多少个节点

方法一、回溯法：两种写法都行

回溯法思路：cnt 逐步记录层数，当遍历到 第k层时，就记录 ans++ 表示第k层节点又多一个

// 回溯法：两种写法都行
int ans = 0, cnt = 1;
// cnt 为 当前在第几层
// ans 记录第 k 层有多少个节点// 有返回值写法
int KNum(BTNode* root, int k, int cnt)
{if (root == NULL) return 0;if (cnt == k) {  // 若默认开始层为 第0层, 传过来的 cnt == 0 这里就是 cnt == k-1,ans++;return 0;}KNum(root->Left, k, cnt + 1);KNum(root->Right, k, cnt + 1);return ans;
}// 无返回值写法
int cnt = 1; // 默认从第一层开始
void KNum(BTNode* root, int k) {if (root == NULL) return;if (cnt == k) {ans++;return;}cnt++;KNum(root->Left, k);cnt--;cnt++;KNum(root->Right, k);cnt--;
}

方法二、递归分治法

递归分治两部曲：1.子问题；2.返回条件

1.子问题：每一个节点都代表 以当前节点为根的 子树一共有多少个第 k 层节点：左子树第 k 层节点个数 + 右子树第 k 层节点个数

2.返回条件：到了第 k 层, 算一个节点，直接返回 1 :代表找到该层一个节点

// 递归分治法：
// 注意 cnt 为当前层数：初始化值为 1：即 根节点默认为 第一层
int KNum(BTNode* root, int k, int cnt)
{if (root == NULL) return 0;if (cnt == k) {   // 到了第 k 层, 算一个节点，直接返回return 1;}return KNum(root->Left, k, cnt + 1) + KNum(root->Right, k, cnt + 1);
}

---

---

四、Find 查找 x 所在的节点

查找功能有两种类型：

1、找到 x 的节点位置，返回指针；

2、找到 x 就返回 true，即只用看 x 在不在

---

1、找到 x 的节点位置，返回指针；

方法一：前序遍历

bool flag = false;
BTNode* tmp;  // tmp 要么就传地址调用，要么开全局变量，要么使用静态，千万别直接作为 形参传进函数中
BTNode* Find(BTNode* root, int x) {if (root == NULL) {return NULL;}if (flag) return tmp;if (root->value == x) {  // 若找到了，将 flag 置为true，便于上一行的 if(flag) 将递归函数一直回退出去flag = true;tmp = root;  // 临时变量 tmp 记录 root return tmp;}Find(root->Left, x);Find(root->Right, x);return NULL;  // 最后都没有 return 回去，说明都找不到，这里就 return NULL
}

---

方法二：递归

递归分治两部曲：1.子问题；2.返回条件

1.子问题：以当前节点为 根的子树，是否找到 == 左子树是否找到 或 右子树是否找到

2.返回条件：一旦找到 目标，返回该节点的 地址，即 root

// 方法二：BTNode* Find(BTNode* root, int x) {if (root == NULL) {return NULL;}if (root->value == x) {return root;}BTNode* res1 = Find(root->Left, x);if (res1) return res1;BTNode* res2 = Find(root->Right, x);if (res2) return res2;return NULL; // 最后谁也没找到，就返回 NULL; 
}

2、找到 x 就返回 true，即看 x 在不在

按位或 || : 只要 一个找到 return true, 另一个就不会进行了，直接总体 return true

一旦函数 Find() 存在一次 true 就会 一直 return 到最外层，直到返回到 main 函数中，

bool Find(BTNode* root, int x)
{if (root == NULL) return false;if (root->value == x) return true;return Find(root->Left, x) || Find(root->Right, x);
}

---

---

五、Leaves 计算 叶子节点个数

其实这个算法 和 【KNum 计算第 k 层有多少个节点】是一样的，只是 ”2.返回条件“ 不同罢了

方法一：

int ansLeaves = 0;
void  Leaves(BTNode* root)
{if (root == NULL)return;if (root->Left == NULL && root->Right == NULL) {ansLeaves++;return;}Leaves(root->Left);Leaves(root->Right);
}

方法二：递归分治法

1.子问题：叶子节点总数 = 左子树叶子节点数量 + 右子树叶子节点数量

2.返回条件：到叶子节点就 return 1 代表找到一个

int Leaves(BTNode* root)
{if (root == NULL) return 0;if (root->Left == NULL && root->Right == NULL) return 1;return Leaves(root->Left) + Leaves(root->Right);
}

---

---

六、Destroy 二叉树的销毁

前序遍历可以销毁，但是相对比较麻烦

前序销毁，销毁当前根节点前，必须先保存前后节点，再递归，相对麻烦

最优选择是 后序遍历

// 采用后序遍历 // 错误写法：不能直接对 root 置为空指针，此处的root是形参
void TreeDestroy(BTNode* root)
{if (root == NULL) return;TreeDestroy(root->Left);TreeDestroy(root->Right);free(root);root = NULL;   // 不能直接对 root 置为空指针，此处的root是形参
}// 两种正确写法：1.传二级指针；2.函数里面只free节点，在外面再将根节点（第一个根）置为空
void TreeDestroy(BTNode* root)
{if (root == NULL) return;TreeDestroy(root->Left);TreeDestroy(root->Right);free(root); // 函数里面只free节点
}
/*
int main()
{// .....TreeDestroy(root);root = NULL;  // 在外面再将根节点（第一个根）置为空
}
*/
// 

---

为什么只需要对第一个根节点置空，而二叉树内部的其他根节点无需置空呢？

解释：平时我们需要指针置为空原因是：我们自己的程序操作，可能会不小心再次使用到 free掉的那片空间的指针，从而出错（指针不为空，但空间又被释放了，（你的房间钥匙还在，但是你的房间 却被炸没了（doge），那你的再次使用钥匙，就会使系统出错）），因此要置空，而本题中人为已经取不到里面的指针了，一般出不了错，（将你的房间给释放掉，房间钥匙给置为NULL之后，这样你原本房间里面 的若有个柜子 即使有该柜子钥匙，你也拿不到钥匙了（注：该柜子钥匙和在房间里面），也就一般不会出错了）所以只关心空间有没有 free 掉（防止内存泄露）就行了

当最后一个节点的内存被释放后，整个二叉树已经不存在了。于是我们在外部将表示整棵树的指针设置为NULL，是为了确保后续操作不会误操作一个已经销毁的树结构，（即先炸掉房子，再丢掉房子的钥匙）

---

---

七、IsCompleteBinaryTree 判断是否为完全二叉树

以下两种方法都基于 层序遍历：bfs

前言：

完全二叉树有个特性：从第一个非空节点到最后一个非空节点，中间是不可能出现 空节点 的

方法一：中途判断

我写的

思路：先算二叉树的非空节点个数，再层序遍历二叉树，每遍历过一个非空节点，k–，

当中途遇到一个 NULL，但是 k>0 (表示 非空节点 的 连续序列 中出现了一个 NULL：即代表该二叉树不是完全二叉树)

// 层序遍历：就是用 bfs
BTNode* arr[2];
bool IsCompleteBinaryTree(BTNode* root, int k)
{Queue q;QueueInit(&q);if (root != NULL) {QueuePush(&q, root);}while (!QueueEmpty(&q)) {BTNode* tmp = QueueFront(&q);QueuePop(&q);if (tmp != NULL) {printf("%d ", tmp->value);k--;}else {if (k > 0) return false;  //  当中途遇到一个 NULL，但是 k>0 ，代表该二叉树不是完全二叉树continue;}arr[0] = tmp->Left, arr[1] = tmp->Right;for (int i = 0; i < 2; ++i) {BTNode* t = arr[i];//if (t == NULL) continue; // 不阻碍 t 为 NULL的继续，否则就难判断中途有无NULL了QueuePush(&q, t);}}printf("\n");QueueDestory(&q);return true;
}

int main()
{BTNode* root = TreeCreate();// 算二叉树的非空节点个数int size = Size(root);  // 这是章节前面 计算二叉树节点个数的函数 Size()bool flag = IsCompleteBinaryTree(root, size);if (flag) printf("Ture\n");else printf("False\n");
}

方法二：遇到N再向后判断

老师的

思路：一直层序遍历，遇到 NULL break循环，再继续向后遍历，一旦遇到一个非空的，就 不是完全二叉树了

BTNode* arr[2];
bool IsCompleteBinaryTree(BTNode* root)
{Queue q;QueueInit(&q);if (root != NULL) {QueuePush(&q, root);}while (!QueueEmpty(&q)) {BTNode* tmp = QueueFront(&q);QueuePop(&q);if (tmp != NULL) {printf("%d ", tmp->value);}else break;arr[0] = tmp->Left, arr[1] = tmp->Right;for (int i = 0; i < 2; ++i) {BTNode* t = arr[i];//if (t == NULL) continue; // 不阻碍 t 为 NULL的继续，否则就难判断中途有无NULL了QueuePush(&q, t);}}// 循环遍历判断后面是否有非空节点while (!QueueEmpty(&q)) {BTNode* t = QueueFront(&q);QueuePop(&q);if(t != NULL)return false;}printf("\n");QueueDestory(&q);return true;
}

---