C算法
递归算法核心：二叉树遍历与结构判断实现
递归算法在二叉树结构判断中应用广泛，涵盖单值二叉树检测、两棵树是否相同判断、子树匹配及对称性验证。核心思路是通过递归遍历根节点与子节点数值及结构进行比对，利用递进匹配与返回逻辑完成整体判定。C 语言实现示例展示了基础递归模板，时间复杂度 O(N)。
递归算法在二叉树结构判断中应用广泛，涵盖单值二叉树检测、两棵树是否相同判断、子树匹配及对称性验证。核心思路是通过递归遍历根节点与子节点数值及结构进行比对，利用递进匹配与返回逻辑完成整体判定。C 语言实现示例展示了基础递归模板，时间复杂度 O(N)。
递归是处理树形结构的重要方法。本文将介绍四种基于递归的二叉树问题，涵盖单值检测、相同性判断、子树匹配及对称性验证。
先对简单二叉树进行算法推理，再推广到整体。
递归规则：先递进再返回。 递进：首先从根节点 root 开始，左子树如果存在先对左子树匹配判断：若二者数值不相等，就返回 false，反之继续对右子树进行判断：二者数值不相等，返回 false。当然，根节点为空返回 true。推广到整体，就遍历左右子树判断。 返回：整个二叉树已经递进判断完毕，要对函数从最后开始返回：看图示，第 2 节点的左右子节点（&&的和关系）为空，那么都返回 true，代表这个子树是单值的。右子树第 3 节点也是单值的。那么根节点的两个子树就都返回 true（&&的和关系），代表整体是单值二叉树。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool isUnivalTree(struct TreeNode* root) {
// 首先判断树是否为空
if (root == NULL) {
return true;
}
// 存在左子树再匹配
if (root->left && root->val != root->left->val) {
return false;
}
if (root->right && root->val != root->right->val) {
return false;
}
return isUnivalTree(root->left) && isUnivalTree(root->right);
}
| 情况分类 | 两根节点情况 | 结果 |
|---|---|---|
| 1 | 两个根节点都为空 | 是相同的树 |
| 2 | 一个根节点为空，另一个不为空 | 不是相同的树 |
| 3 | 两个根节点都不为空 | 比较节点数值进一步判断 |
--根据函数递归规则： 递进：从两个树根节点进行对比，第 1 种情况两个根节点都为空（代表没有子节点）就返回 true；第 2 种情况一个根节点为空，另一个根节点不为空，两个树的结构不同，就返回 false；第 3 种情况两个根节点都不为空，那么就要判断两个节点的数值，不相等就返回 false。最后开始调用函数对比二者的左右子树。 返回：从函数的最后开始返回。看图示，从二者的第 2 个节点的左右子树开始对比，左右节点都为空返回 true（&&的和关系），代表两个二叉树的第 2 节点为根节点子树为相同的树。同理，二者的以第 3 个节点为根节点的子树也是相同的树。以此类推，根节点的左右子树都是相同的树（&&的关系），代表两个二叉树为相同的二叉树。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
// 两个根节点都为空-->结构相同
if (p == NULL && q == NULL) {
return true;
}
// 只有一个根节点为空-->结构不同
if (p == NULL || q == NULL) {
return false;
}
// 两个根节点都不为空，但值不相等
if (p->val != q->val) {
return false;
}
// 否则继续遍历判断子树
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
基本算法：首先，如果根节点为空，就不需要与目标树再进行对比。不为空，就利用前面实现的判断是否是相同的树接口进行判断。不匹配，就调用函数遍历子树（注意：当左子树匹配成功，就不需要再对右子树进行判断）。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
typedef struct TreeNode TreeNode;
bool isSametree(TreeNode* p, TreeNode* q) {
// 第 1 种情况，两个书都为空
if (p == NULL && q == NULL) {
return true;
}
// 第 2 种情况，其中 1 个根节点为空
if (p == NULL || q == NULL) {
return false;
}
// 第 3 种情况，2 个根节点存在，但是数值不相同
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 (root == NULL) {
return false;
}
// 调用判断最开始时根节点是否匹配
if (isSametree(root, subRoot)) {
return true;
}
// 根节点不匹配，向下递归调用
return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
首先根节点为空，代表树为空，一定是对称的。不为空，将根节点的左右子树判断结构是否对称——>改变一下前面实现相同的树的接口：return isSametree(p->left, q->right) && isSametree(p->right, q->left);，因为让左右对应进行对比。
如果函数判断后，返回的 false，那么就直接返回 false。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
typedef struct TreeNode TreeNode;
bool isSametree(TreeNode* p, TreeNode* q) {
// 根节点都为空
if (p == NULL && q == NULL) {
return true;
}
// 一个根节点为空
if (p == NULL || q == NULL) {
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 true;
}
// 树不为空，将左右子树进行对比，看结构是否对称
if (isSametree(root->left, root->right)) {
return true;
}
return false;
}
递归分神的精髓在于层层分化直至洞悉所有脉络。四大递归心法已传授完毕，但这只是算法修真的起点。递归分神的精髓，将在后续的图论、动态规划等秘境中继续发挥威力。保持这份求道之心，我们下期「回溯秘境」再会！愿每一位码农修行者，都能在算法之道上突破自我。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online