当前位置： 首页 > web >正文

二叉树OJ习题

web 2025/9/8 4:12:17

目录

一. Leetcode 965 单值二叉树

思路

代码实现

二. Leetcode 100 相同的树

思路

代码实现

三. Leetcode 101 对称二叉树

思路

代码实现

四. Leetcode 572 另一棵树的子树

思路

代码实现

五. Leetcode 二叉树遍历

5.1  Leetcode 144 二叉树的前序遍历

思路

代码实现

5.2  Leetcode 94 二叉树的中序遍历

思路

代码实现

5.3  Leetcode 145 二叉树的后序遍历

思路

代码实现

六.  牛客网 二叉树的构建及遍历

思路

代码实现

一. Leetcode 965 单值二叉树

https://leetcode.cn/problems/univalued-binary-tree/description/

思路

  • 若树为空（root 为 NULL），则是单值二叉树，返回 true
  • 若当前节点存在左子节点且左子节点值与当前节点值不同，返回 false
  • 若当前节点存在右子节点且右子节点值与当前节点值不同，返回 false
  • 递归检查左子树和右子树是否都是单值二叉树，只有两者都为单值二叉树时，当前树才是单值二叉树

代码实现

bool isUnivalTree(struct TreeNode* root) {//判断节点是否为空if(root==NULL){return true;}//左孩子存在并且值不等于其父节点值时，返回falseif(root->left && root->left->val != root->val){return false;}//右孩子存在并且值不等于其父节点值时，返回falseif(root->right && root->right->val != root->val){return false;}//递归左右子树，只有都为单值二叉树时，返回falsereturn isUnivalTree(root->left) && isUnivalTree(root->right);
}

二. Leetcode 100 相同的树

https://leetcode.cn/problems/same-tree/description/

思路

  • 若两棵树的当前节点都为空（p 和 q 均为 NULL），则这两个节点相同，返回 true
  • 若其中一棵树的当前节点为空而另一棵不为空（p 为 NULL 或 q 为 NULL），则说明两树结构不同，返回 false
  • 当两棵树的节点都不为空时，比较当前节点的值是否相同，若不同，则返回false，
  • 递归检查两树的左子节点是否相同，且右子节点是否相同，只有两者都相同时才返回 true，有一个不同就返回false

代码实现

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

三. Leetcode 101 对称二叉树

https://leetcode.cn/problems/symmetric-tree/description/

思路（运用相同二叉树的思想）

利用递归和镜像比较的特性，将对称树判断转化为特殊的两棵树比较问题。

1. 对称二叉树的核心是判断左子树与右子树是否镜像对称

2. 镜像对称的判断通过改造 "相同树" 的逻辑实现：

  • 比较左子树的左节点与右子树的右节点
  • 比较左子树的右节点与右子树的左节点

3. 具体步骤：

  • 若两节点都为空，则返回 true
  • 若其中一节点为空另一不为空，则返回 false
  • 若两节点值不相等，则返回 false
  • 递归检查左子树左节点与右子树右节点、左子树右节点与右子树左节点是否都对称

4. 对原树调用时，只需检查其左子树与右子树是否镜像对称

代码实现

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->right) && isSameTree(p->right,q->left);
}bool isSymmetric(struct TreeNode* root) {return isSameTree(root->left,root->right);
}

四. Leetcode 572 另一棵树的子树

https://leetcode.cn/problems/subtree-of-another-tree/description/

思路（运用相同二叉树的思想）

判断 subRoot 是否为 root 的子树，即检查 root 中是否存在与 subRoot 完全相同的子树

通过递归遍历主树的每个节点，将每个节点作为子树根节点与目标子树进行比对，一旦找到匹配则返回 true。

递归逻辑：

  • 若当前 root 为空，返回 false（空树不可能包含子树）
  • 若当前 root 节点为根的子树与 subRoot 相同，返回 true
  • 否则递归检查 root 的左子树或右子树是否包含 subRoot

利用 isSameTree 函数（相同二叉树）检查两棵树是否完全相同

  • 两树都为空则相同
  • 只有一树为空则不同
  • 节点值不同则不同
  • 递归比较左右子树是否都相同

代码实现

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

五. Leetcode 二叉树的遍历

5.1  Leetcode 144 二叉树的前序遍历

https://leetcode.cn/problems/binary-tree-preorder-traversal/description/

思路

通过先获取树的大小来精确分配内存，再利用递归按前序规则遍历并存储节点值，最终返回完整的遍历结果数组。

1.前序遍历顺序为：根节点 → 左子树 → 右子树

2.实现步骤：

  • 先计算二叉树节点总数（用于分配数组空间）
  • 动态开辟数组空间用于存储遍历结果
  • 通过递归函数完成前序遍历
  • 若节点为空则返回
  • 先访问当前节点（将值存入数组）
  • 递归遍历左子树
  • 递归遍历右子树

3.使用指针记录数组填充位置，确保递归过程中正确更新索引

代码实现

 typedef struct TreeNode TreeNode;//二叉树节点个数
int BinaryTreeSize(TreeNode* root)
{if(root==NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
//前序遍历
//传下标的指针，在递归过程中能够改变
void PreOrder(TreeNode* root,int* arr,int* pi)
{if(root==NULL){return;}arr[(*pi)++]=root->val;PreOrder(root->left,arr,pi);PreOrder(root->right,arr,pi);
}int* preorderTraversal(struct TreeNode* root, int* returnSize) {//*returnSize表示数组元素个数,也就是二叉树节点个数*returnSize = BinaryTreeSize(root);int* arr=(int*)malloc(sizeof(int)*(*returnSize));int i=0;PreOrder(root,arr,&i);return arr;
}

5.2  Leetcode 94 二叉树的中序遍历

https://leetcode.cn/problems/binary-tree-inorder-traversal/description/

思路

通过先获取树的大小来精确分配内存，再利用递归按中序规则遍历并存储节点值，最终返回完整的遍历结果数组。

1.中序遍历顺序为：左子树 → 根节点 → 右子树

2.实现步骤：

  • 先计算二叉树节点总数（用于分配数组空间）
  • 动态开辟数组空间用于存储遍历结果
  • 通过递归函数完成中序遍历
  • 若节点为空则返回
  • 先递归遍历左子树
  • 访问当前节点（将值存入数组）
  • 递归遍历右子树

3.使用指针记录数组填充位置，确保递归过程中正确更新索引

代码实现

typedef struct TreeNode TreeNode;//二叉树节点个数
int BinaryTreeSize(TreeNode* root)
{if(root==NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}//传下标的指针，在递归过程中能够改变
void InOrder(TreeNode* root,int* arr,int* pi)
{if(root==NULL){return;}InOrder(root->left,arr,pi);arr[(*pi)++]=root->val;InOrder(root->right,arr,pi);
}int* inorderTraversal(struct TreeNode* root, int* returnSize) {//*returnSize表示数组元素个数,也就是二叉树节点个数*returnSize = BinaryTreeSize(root);int* arr=(int*)malloc(sizeof(int)*(*returnSize));int i=0;InOrder(root,arr,&i);return arr;
}

5.3  Leetcode 145 二叉树的后序遍历

https://leetcode.cn/problems/binary-tree-postorder-traversal/description/

思路

通过先获取树的大小来精确分配内存，再利用递归按中序规则遍历并存储节点值，最终返回完整的遍历结果数组。

1.中序遍历顺序为：左子树 → 右子树 → 根节点

2.实现步骤：

  • 先计算二叉树节点总数（用于分配数组空间）
  • 动态开辟数组空间用于存储遍历结果
  • 通过递归函数完成后序遍历
  • 若节点为空则返回
  • 先递归遍历左子树
  • 再递归遍历右子树
  • 访问当前节点（将值存入数组）

3.使用指针记录数组填充位置，确保递归过程中正确更新索引

代码实现

typedef struct TreeNode TreeNode;//二叉树节点个数
int BinaryTreeSize(TreeNode* root)
{if(root==NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}//传下标的指针，在递归过程中能够改变
void PostOrder(TreeNode* root,int* arr,int* pi)
{if(root==NULL){return;}PostOrder(root->left,arr,pi);PostOrder(root->right,arr,pi);arr[(*pi)++] = root->val;
}int* postorderTraversal(struct TreeNode* root, int* returnSize) {//*returnSize表示数组元素个数,也就是二叉树节点个数*returnSize=BinaryTreeSize(root);int* arr=(int*)malloc(sizeof(int)*(*returnSize));//按后序遍历将二叉树中的数据存储在数组int i=0;PostOrder(root,arr,&i);return arr;
}

六.  牛客网 二叉树的构建及遍历

https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef

思路

通过递归复用先序遍历的逻辑构建二叉树，再用递归完成中序遍历，清晰映射二叉树的递归特性

1. 数据结构定义：定义二叉树节点结构（含数据域、左子树指针、右子树指针）

2. 节点创建：实现buyNode函数，动态分配节点内存并初始化（数据域赋值，左右指针置空）

3. 二叉树构建（核心）：

  • 基于先序遍历字符串递归构建：遇到 '#' 表示空节点，返回 NULL
  • 非 '#' 字符则创建当前节点，递归构建左子树，再递归构建右子树
  • 用指针pi记录当前处理的字符串索引，确保递归中同步推进

4. 中序遍历：递归实现左子树→根节点→右子树的遍历顺序，打印节点数据

5. 主流程：

  • 读取用户输入的先序字符串
  • 调用构建函数生成二叉树
  • 执行中序遍历并输出结果

代码实现

#include <stdio.h>
#include <stdlib.h>//定义二叉树节点结构
typedef struct BinaryTreeNode{char data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;//申请新节点
BTNode* buyNode(char x)
{BTNode* newnode=(BTNode*)malloc(sizeof(BTNode));if(newnode==NULL){perror("malloc fail!");exit(1);}newnode->data=x;newnode->left=newnode->right=NULL;return newnode;
}//构建二叉树
BTNode* creatBinaryTree(char* arr,int* pi)
{if(arr[*pi]=='#'){(*pi)++;return NULL;}BTNode* root=buyNode(arr[(*pi)++]);root->left=creatBinaryTree(arr, pi);root->right=creatBinaryTree(arr, pi);return root;
}//中序遍历
void InOrder(BTNode* root)
{if(root==NULL){return;}InOrder(root->left);printf("%c ",root->data);InOrder(root->right);
}int main() {//输入字符串存储起来char arr[100];scanf("%s",arr);//按前序遍历构建二叉树int i=0;BTNode* root = creatBinaryTree(arr, &i);//中序遍历InOrder(root);return 0;
}

总结

本文围绕二叉树 OJ 习题展开，涵盖了单值二叉树、相同二叉树、对称二叉树、子树判断及遍历等经典问题。通过递归等核心思想，解析了各题的解题思路与实现逻辑，帮助读者掌握二叉树的特性及常见操作，为应对同类问题提供了清晰的思路与方法。

如果大家在练习中发现新的解题角度，或是有没搞懂的知识点，欢迎在评论区留言讨论。后续我也会持续更新数据结构相关的 OJ 解析，咱们一起在刷题中夯实基础，稳步进阶！

http://www.xdnf.cn/news/19614.html

相关文章：

  • Azure AI Search构建RAG的优化点
  • 动态配置最佳实践：Spring Boot 十种落地方式与回滚审计指南（含实操与避坑）
  • Hello World背后的秘密：详解 C++ 编译链接模型
  • 【重学MySQL】九十三、MySQL字符集与比较规则完全解析
  • Python轻量化革命：用MicroPython构建边缘智能设备
  • 【开题答辩全过程】以 基于SpringBoot的流浪猫狗领养系统为例，包含答辩的问题和答案
  • Unity学习----【数据持久化】二进制存储（二）--文件流
  • 大模型RAG项目实战：Milvus向量数据库
  • 实现自己的AI视频监控系统-第三章-信息的推送与共享1
  • Bootloader（1）：初步认识Bootloader概念（什么是Bootloader）
  • 基于muduo库的图床云共享存储项目（三）
  • Ansible配置文件与主机清单
  • juicefs+ceph rgw 存储安装
  • MYSQL表的增删改查
  • 深入解析数据结构之单链表
  • ros2bag_py的api小结、丢帧问题对策
  • 【Linux基础】Linux系统启动：深入理解GRUB引导程序
  • 平面椭圆转化为三阶Bezier曲线的方法
  • 并发编程——10 CyclicBarrier的源码分析
  • 大模型参数到底是什么？
  • synchronized的锁对象 和 wait，notify的调用者之间的关系
  • EKS上部署gpu服务利用karpenter实现自动扩缩（s3作为共享存储）
  • 一、计算机系统知识
  • C++ 枚举算法详细利用与数字分解教学教案
  • Spring Security 6.x 功能概览与代码示例
  • 程序员独立开发直播卖产品 SOP 教程
  • arm容器启动spring-boot端口报错
  • 基于开源AI大模型、AI智能名片与S2B2C商城小程序的“教育用户”模式探究
  • 谈谈对BFC的理解
  • 当代科学（范畴大辩论） 的学科分科（论据）的要素论（论点）及方法论（论证）：边缘处理