?前言
二叉树是数据结构中的重要概念，在算法和编程中有着广泛的应用。以下是十大经典的二叉树题目及其解析与 C 语言代码实现，同时也会说明题目来源。
二叉树的基本概念?【剖析二叉树】
目录
?二叉树的遍历
⭐前序遍历
⭐中序遍历
⭐ 后序遍历
?二叉搜索树相关
⭐验证二叉搜索树
⭐二叉搜索树的插入
⭐二叉搜索树的删除
?二叉树的高度与平衡
⭐计算二叉树的高度
⭐平衡二叉树
?二叉树的路径问题
⭐二叉树的所有路径
⭐路径总和
?总结
?二叉树的遍历
⭐前序遍历
题目链接?【力扣】
题目描述：按照根节点 - 左子树 - 右子树的顺序遍历二叉树，并输出节点值。C 语言代码实现：#include <stdio.h>#include <stdlib.h>// 定义二叉树节点结构typedef struct TreeNode { int val; struct TreeNode* left; struct TreeNode* right;} TreeNode;// 创建新节点TreeNode* createNode(int val) { TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode)); newNode->val = val; newNode->left = NULL; newNode->right = NULL; return newNode;}// 前序遍历递归函数void preorderTraversal(TreeNode* root) { if (root == NULL) { return; } printf("%d ", root->val); preorderTraversal(root->left); preorderTraversal(root->right);}createNode函数用于动态分配内存并创建一个新的二叉树节点，初始化节点的值以及左右子树指针为NULL。preorderTraversal是前序遍历的递归实现。首先检查根节点是否为NULL，如果是则直接返回。然后输出根节点的值，接着递归地对左子树进行前序遍历，再对右子树进行前序遍历。这样就按照根节点 - 左子树 - 右子树的顺序访问了二叉树的所有节点。 ?前序遍历递归图解：
⭐中序遍历
题目链接?【力扣】
题目描述：以左子树 - 根节点 - 右子树的顺序遍历二叉树并输出节点值。C 语言代码实现// 中序遍历递归函数void inorderTraversal(TreeNode* root) { if (root == NULL) { return; } inorderTraversal(root->left); printf("%d ", root->val); inorderTraversal(root->right);}
⭐ 后序遍历
题目链接?【力扣】
题目描述：按照左子树 - 右子树 - 根节点的顺序遍历二叉树并输出节点值。C 语言代码实现// 后序遍历递归函数void postorderTraversal(TreeNode* root) { if (root == NULL) { return; } postorderTraversal(root->left); postorderTraversal(root->right); printf("%d ", root->val);}
?二叉搜索树相关
⭐验证二叉搜索树
题目链接?【力扣】
题目描述：判断给定的二叉树是否是二叉搜索树。有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树 C 语言代码实现// 验证二叉搜索树的辅助函数int isValidBSTHelper(TreeNode* root, TreeNode** prev) { if (root == NULL) { return 1; } if (!isValidBSTHelper(root->left, prev)) { return 0; } if (*prev!= NULL && root->val <= (*prev)->val) { return 0; } *prev = root; return isValidBSTHelper(root->right, prev);}// 验证二叉搜索树的函数接口int isValidBST(TreeNode* root) { TreeNode* prev = NULL; return isValidBSTHelper(root, &prev);}isValidBSTHelper是验证二叉搜索树的核心递归函数。它首先递归地检查左子树是否是二叉搜索树，如果不是则直接返回0。然后检查当前节点的值是否大于前一个节点的值（对于中序遍历顺序），如果不满足则返回0。接着更新前一个节点为当前节点，并递归地检查右子树是否是二叉搜索树。isValidBST函数是对外提供的接口函数，它初始化一个prev指针为NULL，然后调用isValidBSTHelper函数开始验证。
⭐二叉搜索树的插入
题目链接?【力扣】
题目描述：在二叉搜索树中插入一个新的节点。C 语言代码实现// 向二叉搜索树中插入节点TreeNode* insertIntoBST(TreeNode* root, int val) { if (root == NULL) { return createNode(val); } if (val < root->val) { root->left = insertIntoBST(root->left, val); } else { root->right = insertIntoBST(root->right, val); } return root;}NULL，则创建一个新节点并插入。最后返回更新后的根节点。
⭐二叉搜索树的删除
题目链接?【力扣】
题目描述：从二叉搜索树中删除一个指定节点，并保持二叉搜索树的性质。C 语言代码实现// 找到二叉搜索树中的最小节点TreeNode* findMin(TreeNode* node) { while (node->left!= NULL) { node = node->left; } return node;}// 删除二叉搜索树中的节点TreeNode* deleteNode(TreeNode* root, int key) { if (root == NULL) { return root; } if (key < root->val) { root->left = deleteNode(root->left, key); } else if (key > root->val) { root->right = deleteNode(root->right, key); } else { if (root->left == NULL) { TreeNode* temp = root->right; free(root); return temp; } else if (root->right == NULL) { TreeNode* temp = root->left; free(root); return temp; } TreeNode* minNode = findMin(root->right); root->val = minNode->val; root->right = deleteNode(root->right, minNode->val); } return root;}findMin函数用于在二叉搜索树中找到最小节点，即一直沿着左子树找到最左边的节点。deleteNode函数是删除节点的主要函数。首先找到要删除的节点，如果节点不存在则直接返回当前树。如果要删除的节点是叶子节点，直接删除并返回其非空子树（如果有）。如果节点只有一个子节点，将子节点替换该节点并释放原节点内存。如果节点有两个子节点，找到该节点右子树中的最小节点，将其值赋给要删除的节点，然后删除右子树中的最小节点。
?二叉树的高度与平衡
⭐计算二叉树的高度
题目链接?【力扣】
题目描述：求二叉树的高度，即从根节点到最远叶子节点的最长路径上的节点数。C 语言代码实现// 计算二叉树的高度int treeHeight(TreeNode* root) { if (root == NULL) { return 0; } int leftHeight = treeHeight(root->left); int rightHeight = treeHeight(root->right); return (leftHeight > rightHeight? leftHeight : rightHeight) + 1;}NULL，如果是则高度为0。然后分别递归地计算左子树和右子树的高度，取两者中的较大值加1作为整棵树的高度。加1是因为要加上根节点本身。
⭐平衡二叉树
题目链接?【力扣】
题目描述：判断一棵二叉树是否是平衡二叉树（左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树）。C 语言代码实现// 判断二叉树是否平衡的辅助函数int isBalancedHelper(TreeNode* root, int* height) { if (root == NULL) { *height = 0; return 1; } int leftHeight, rightHeight; if (!isBalancedHelper(root->left, &leftHeight)) { return 0; } if (!isBalancedHelper(root->right, &rightHeight)) { return 0; } *height = (leftHeight > rightHeight? leftHeight : rightHeight) + 1; if (abs(leftHeight - rightHeight) > 1) { return 0; } return 1;}// 判断二叉树是否平衡的函数接口int isBalanced(TreeNode* root) { int height; return isBalancedHelper(root, &height);}isBalancedHelper函数是判断平衡二叉树的核心递归函数。首先处理空树的情况，将高度设置为0并返回1表示空树是平衡的。然后递归地计算左子树和右子树的高度，并检查它们的高度差是否超过1，同时递归地检查左子树和右子树是否本身是平衡的。isBalanced函数是对外接口，它初始化一个高度变量，然后调用isBalancedHelper函数进行判断并返回结果。
?二叉树的路径问题
⭐二叉树的所有路径
题目链接?【力扣】
题目描述：输出二叉树从根节点到所有叶子节点的路径。C 语言代码实现#include <string.h>// 二叉树的所有路径辅助函数void binaryTreePathsHelper(TreeNode* root, char** paths, int* pathCount, char* currentPath, int pathLen) { if (root == NULL) { return; } currentPath[pathLen] = root->val + '0'; currentPath[pathLen + 1] = '\0'; if (root->left == NULL && root->right == NULL) { paths[*pathCount] = (char*)malloc((pathLen + 2) * sizeof(char)); strcpy(paths[*pathCount], currentPath); (*pathCount)++; } binaryTreePathsHelper(root->left, paths, pathCount, currentPath, pathLen + 1); binaryTreePathsHelper(root->right, paths, pathCount, currentPath, pathLen + 1);}// 二叉树的所有路径函数接口char** binaryTreePaths(TreeNode* root, int* returnSize) { char** paths = (char**)malloc(100 * sizeof(char*)); // 假设最多有100条路径，可根据实际情况调整 int pathCount = 0; char currentPath[1000]; // 假设路径长度最大为1000，可根据实际情况调整 binaryTreePathsHelper(root, paths, &pathCount, currentPath, 0); *returnSize = pathCount; return paths;}binaryTreePathsHelper函数是实现输出所有路径的递归辅助函数。首先处理空节点情况，直接返回。然后将当前节点的值添加到路径字符串中，并检查当前节点是否为叶子节点，如果是则将当前路径复制到结果数组中并更新路径计数。接着递归地对左子树和右子树进行处理，每次将路径长度加1。binaryTreePaths函数是对外接口，它分配内存用于存储路径结果，初始化相关变量，然后调用binaryTreePathsHelper函数进行计算，并返回路径数组和路径数量。
⭐路径总和
题目链接?【力扣】
题目描述：给定一棵二叉树和一个整数，判断是否存在从根节点到叶子节点的路径，使得路径上所有节点值之和等于给定的整数。C 语言代码实现// 路径总和辅助函数int hasPathSumHelper(TreeNode* root, int targetSum, int currentSum) { if (root == NULL) { return 0; } currentSum += root->val; if (root->left == NULL && root->right == NULL && currentSum == targetSum) { return 1; } return hasPathSumHelper(root->left, targetSum, currentSum) || hasPathSumHelper(root->right, targetSum, currentSum);}// 路径总和函数接口int hasPathSum(TreeNode* root, int targetSum) { return hasPathSumHelper(root, targetSum, 0);}hasPathSumHelper函数是判断路径总和的递归辅助函数。首先处理空节点情况，返回0表示当前路径不符合条件。然后将当前节点的值加到当前路径和中，检查当前节点是否为叶子节点且路径和是否等于目标和，如果是则返回1表示找到符合条件的路径。最后递归地对左子树和右子树进行检查，只要左子树或右子树中有符合条件的路径，就返回1。hasPathSum函数是对外接口，它初始化当前路径和为0，然后调用hasPathSumHelper函数开始判断。
?总结
通过对这十大经典二叉树题目的详细解析和 C 语言代码实现，希望读者能够更深入地理解二叉树的相关知识和算法，提升在数据结构和算法方面的编程能力和问题解决能力。
无论是在学习过程中还是应对实际的编程挑战，这些知识都将具有重要的价值。
???感谢你看到最后，点个赞再走吧！???