C算法
数据结构：二叉树精选 9 道 OJ 练习
二叉树相关的 9 道经典 OJ 练习题，涵盖前序遍历、最大深度、单值二叉树、相同树、对称二叉树、另一棵树的子树、二叉树遍历、翻转二叉树及平衡二叉树。所有题目均提供基于递归思想的 C 语言代码实现，包含节点统计、深度计算、结构比较等核心逻辑，适合数据结构初学者巩固二叉树遍历与性质判断能力。
二叉树相关的 9 道经典 OJ 练习题，涵盖前序遍历、最大深度、单值二叉树、相同树、对称二叉树、另一棵树的子树、二叉树遍历、翻转二叉树及平衡二叉树。所有题目均提供基于递归思想的 C 语言代码实现，包含节点统计、深度计算、结构比较等核心逻辑，适合数据结构初学者巩固二叉树遍历与性质判断能力。
本文整理了二叉树相关的 9 道经典 OJ 练习题，涵盖常见遍历与性质判断操作。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
// 实现：'二叉树的求树中节点的总个数'操作
int BTSize(struct TreeNode* root) {
// 处理：'空树 + 遍历到空节点'的情况
if (root == NULL)
return 0;
// 递归计算二叉树中节点的个数
return BTSize(root->left) + BTSize(root->right) + 1;
}
// 实现：'二叉树的前序遍历'操作
void PrevOrder(struct TreeNode* root, int* arr, int* pi) {
// 处理：'空树 + 空节点'的情况
if (root == NULL)
return;
// 递归的进行遍历
arr[*pi] = root->val;
(*pi)++;
PrevOrder(root->left, arr, pi);
PrevOrder(root->right, arr, pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
// 思路：
// 1. 先计算出二叉树总的节点数
// 2. 进行前序遍历将遍历的次数存储到数组中
// 动态开辟数组空间
*returnSize = BTSize(root);
int* arr = (int*)malloc(*returnSize * sizeof(int));
int i = 0;
// 先序序列填充数组
PrevOrder(root, arr, &i);
return arr;
}
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
// 问题的本质：二叉树的最大深度=fmax(左子树的深度，右子树的深度)
int maxDepth(struct TreeNode* root) {
// 处理：空树的情况
if (root == NULL)
return 0;
return fmax(maxDepth(root->left), maxDepth(root->right)) + 1;
}
/**
* 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 判断：如果双亲节点的值不等于孩子节点的值
if (root->left && root->left->val != root->val)
return false;
if (root->right && root->right->val != root->val)
return false;
// 在左子树中进行递归
bool ret = isUnivalTree(root->left);
if (!ret)
return false;
// 在右子树中进行递归
ret = isUnivalTree(root->right);
if (!ret)
return false;
// 返回通过所有检测的返回值
return true;
}
/**
* 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 判断：如果的两棵树的节点的值不相等
if (p->val != q->val)
return false;
// 递归判断左子树和右子树的所有节点是否相等
bool ret = isSameTree(p->left, q->left);
if (!ret)
return false;
// 这里是当我们未遍历完所有的节点时就已经出现了节点不匹配的情况的话，我们就先让递归提前结束
ret = isSameTree(p->right, q->right);
if (!ret)
return false;
return true;
}
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool _isSymmetric(struct TreeNode* root1, struct TreeNode* root2) {
// 处理：左子树和右子树都为空树的情况
if (root1 == NULL && root2 == NULL)
return true;
// 处理：左子树和右子树中有一颗树是空树
if (root1 == NULL || root2 == NULL)
return false;
// 处理：左子树和右子树都不为空树，但是对应位置的节点的值却不相等
if (root1->val != root2->val)
return false;
// 进行递归遍历左子树和右子树中的节点
// 比较：'左子树的左孩子 and 右子树的右孩子'
bool ret = _isSymmetric(root1->left, root2->right);
if (!ret)
return false;
// 比较：'左子树的右孩子 and 右子树的左孩子'
ret = _isSymmetric(root1->right, root2->left);
if (!ret)
return false;
return true;
}
bool isSymmetric(struct TreeNode* root) {
// 确保进行判断的这颗树是一颗合法的树
if (!root)
return false;
// 调用子函数解决问题
return _isSymmetric(root->left, root->right);
}
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool isSameTree(struct TreeNode* root1, struct TreeNode* root2) {
// 处理：'空树 + 遍历到空节点' 的情况
if (root1 == NULL && root2 == NULL)
return true;
// 处理：其中一棵树为空树另一棵树不为空树的情况
if (root1 == NULL || root2 == NULL)
return false;
// 处理：两棵树都不为空树但是，但是当前遍历到的节点的值不相等
if (root1->val != root2->val)
return false;
// 进行递归判断两棵树的其他节点
bool ret = isSameTree(root1->left, root2->left);
if (!ret)
return false;
ret = isSameTree(root1->right, root2->right);
if (!ret)
return false;
return true;
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
// 思路：判断一棵树是不是另一棵树的子树
// （1）二叉树的寻找某个节点操作 + （2）判断两棵二叉树是否相等
// 处理：'空树 + 遍历到空节点' 的情况
if (root == NULL)
return false;
// 使用 if 判断：如果我们找到这个节点
if (isSameTree(root, subRoot))
return true;
// 进行递归遍历
// 递归左子树进行寻找
bool ret = isSubtree(root->left, subRoot);
if (ret)
return ret;
// 递归右子树进行寻找
ret = isSubtree(root->right, subRoot);
if (ret)
return ret;
return false;
}
开始挑战：KY11 二叉树遍历
#include <stdio.h>
#include <stdlib.h>
// 二叉树的存储结构
typedef struct BinaryTreeNode {
int data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
} BTNode;
// 实现：'二叉树的中序遍历'操作
void InOrder(BTNode* root) {
// 处理：'空树 + 空节点'的情况
if (root == NULL)
return;
// 递归进行中序遍历
InOrder(root->left);
printf("%c ", root->data);
InOrder(root->right);
}
// 实现：'根据前序遍历字符串创建出一棵二叉树'
BTNode* BTCreate(char* arr, int* pi) {
// 先处理空节点
if (arr[*pi] == '#') {
(*pi)++;
return NULL;
}
// 再处理非空节点
// 使用 malloc 为树节点开辟空间
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
// 为节点进行赋值
root->data = arr[*pi];
(*pi)++;
// 为节点创建结构
root->left = BTCreate(arr, pi);
root->right = BTCreate(arr, pi);
// 返回创建出的二叉树的根节点
return root;
}
int main() {
// 获取数据
char arr[100];
scanf("%s", arr);
int i = 0;
// 处理数据
BTNode* root = BTCreate(arr, &i);
// 输出数据
InOrder(root);
return 0;
}
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
// 实现两个变量的值的交换
// 注意：这里要写 struct 不要忘记了，因为这里的 struct TreeNode 才是 a 的类型啊！！！
void Swap(struct TreeNode** a, struct TreeNode** b) {
// 注意：Swap 函数处理的是树的节点，需要进行判空操作
if (a == NULL && b == NULL)
return;
struct TreeNode* tmp = *a;
*a = *b;
*b = tmp;
}
struct TreeNode* invertTree(struct TreeNode* root) {
// 处理空树的情况（同时也是递归结束的条件 ---> 传入参数的空节点的时候，停止递归）
if (root == NULL)
return NULL;
// 交换遍历到的节点的左右孩子
Swap(&root->left, &root->right);
// 递归处理其他的节点
invertTree(root->left);
invertTree(root->right);
// 将处理后的二叉树的根节点返回
return root;
}
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
//--------------实现求一个求树高度的方法--------------
int BTHeight(struct TreeNode* root) {
// 处理空树的情况（同时也是递归结束的条件 ---> 传入参数的空节点的时候，停止递归）
if (root == NULL)
return 0;
// 递归处理左子树的情况
int leftHeight = BTHeight(root->left);
// 递归处理右子树的情况
int rightHeight = BTHeight(root->right);
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
bool isBalanced(struct TreeNode* root) {
// 思路：
// 1. 遍历的这棵树中的所以节点
// 2. 对遍历到的每个节点的左右子树的根节点调用 BTHeight 函数
// 3. 计算所返回的两个值的差值
// 处理空树的情况（同时也是递归结束的条件 ---> 传入参数的空节点的时候，停止递归）
if (root == NULL)
return true;
/*-------------第一步：求出分别以当前遍历到的节点的左右子树为根节点的树的高度-------------*/
int leftTree = BTHeight(root->left);
int rightTree = BTHeight(root->right);
/*-------------第二步：计算左右子树的高度差-------------*/
if (abs(leftTree - rightTree) > 1) {
return false;
}
/*-------------第三步：递归遍历这棵二叉树中的所有的节点-------------*/
return isBalanced(root->left) && isBalanced(root->right);
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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