二叉树面试题（C 语言）

🕗 发布于 2024-11-14 01:56 c语言 经验分享 数据结构 二叉树面试题

1. 单值二叉树

题目描述： 如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时，才返回 true；否则返回 false。

示例 1：
在这里插入图片描述
输入：[1,1,1,1,1,null,1]
输出：true

示例 2：
在这里插入图片描述
输入：[2,2,2,5,2]
输出：false

提示：

给定树的节点数范围是 [1, 100]。
每个节点的值都是整数，范围为 [0, 99]

题目OJ链接： link

解题思路： 运用递归的思想，把二叉树分成一个个小树。根节点和左右孩子比较，若相同则左右孩子继续和它们的孩子比较，直到空树。遇到空树需要返回 true，因为遇到空树了就证明你这一整棵树都满足单值条件。其中有一组不相同就返回 false，全部相同返回 true。

代码如下：

bool isUnivalTree(struct TreeNode* root) {
    // 空树
    if (NULL == root)
        return true;
    // 根节点和孩子比较
    if (root->left && root->left->val != root->val)
        return false;
    if (root->right && root->right->val != root->val)
        return false;
    // 继续比较左子树和右子树
    return isUnivalTree(root->left)
        && isUnivalTree(root->right);
}

2. 相同的树

题目描述： 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：
在这里插入图片描述
输入：p = [1,2,3], q = [1,2,3]
输出：true

示例 2：
在这里插入图片描述
输入：p = [1,2], q = [1,null,2]
输出：false

示例 3：
在这里插入图片描述
输入：p = [1,2,1], q = [1,1,2]
输出：false

提示：

两棵树上的节点数目都在范围 [0, 100] 内
-10⁴ <= Node.val <= 10⁴

题目OJ链接： link

解题思路： 首先判断根节点，然后再判断左子树，再判断右子树，直到两边都是空树。全部都满足才是相同的树，返回 true；一个地方不满足都是不相同的树，返回 false。

代码如下：

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    // 空树判断
    if (NULL == p && NULL == q)
        return true;
    // 有一颗空树
    if (NULL == p || NULL == q)
        return false;
    // 根节点不同
    if (p->val != q->val)
        return false;
    // 左右子树
    return isSameTree(p->left, q->left)
        && isSameTree(p->right, q->right);
}

3. 对称二叉树

题目描述： 给你一个二叉树的根节点 root ，检查它是否轴对称。

示例 1：
在这里插入图片描述
输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：
在这里插入图片描述
输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100

题目OJ链接： link

解题思路： 对称二叉树根节点的左右子树对称，那么左子树的左子树应该和右子树的右子树对称，左子树的右子树应该和右子树的左子树对称。直到两边都是空树，返回 true。只要有一个不满足，就返回 false。

代码如下：

typedef struct TreeNode TreeNode;

// 左右子树对称判断
bool isSymmetricLeftAndRight(TreeNode* left, TreeNode* right)
{
    // 都是空树
    if (NULL == left && NULL == right)
        return true;
    // 有一颗空树
    if (NULL == left || NULL == right)
        return false;
    // 值不相同
    if (left->val != right->val)
        return false;
    // 对称树比较
    return isSymmetricLeftAndRight(left->left, right->right)
        && isSymmetricLeftAndRight(left->right, right->left);
}

bool isSymmetric(struct TreeNode* root) {
    return isSymmetricLeftAndRight(root->left, root->right);
}

4. 二叉树的前序遍历

题目描述： 给你二叉树的根节点 root ，返回它节点值的前序遍历。

示例 1：

输入：root = [1,null,2,3]

输出：[1,2,3]

解释：
在这里插入图片描述

示例 2：

输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]

输出：[1,2,4,5,6,7,3,8,9]

解释：
在这里插入图片描述

示例 3：

输入：root = []

输出：[]

示例 4：

输入：root = [1]

输出：[1]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

题目OJ链接： link

解题思路： 本题需要动态开辟一个数组用来存储二叉树的前序遍历进行返回，第二个参数需要返回开辟数组的大小。第一步需要计算二叉树的节点个数，然后再开辟空间，返回二叉树的前序遍历。

代码如下：

typedef struct TreeNode TreeNode;

// 返回二叉树节点的个数
size_t TreeSize(TreeNode* root)
{
    // 空树
    if (NULL == root)
        return 0;
    // 返回 1+左右节点的个数
    return 1 + TreeSize(root->left) + TreeSize(root->right);
}

// 记录二叉树的前序遍历
void GetPreOrder(TreeNode* root, int* arr, int* pi)
{
    // 空树
    if (NULL == root)
        return;
    // 记录根节点
    arr[(*pi)] = root->val;
    ++(*pi);
    // 记录左子树
    GetPreOrder(root->left, arr, pi);
    // 记录右子树
    GetPreOrder(root->right, arr, pi);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    // 获得节点个数
    size_t n = TreeSize(root);
    *returnSize = n;
    // 开辟空间
    int* arr = (int*)malloc(sizeof(int)*n);
    // 获得前序遍历
    int i = 0;
    GetPreOrder(root, arr, &i);
    // 返回
    return arr;
}

5. 二叉树的中序遍历

本题和二叉树的前序遍历相似，只给出题目链接和代码。

题目OJ链接： link

代码如下：

typedef struct TreeNode TreeNode;

// 返回二叉树的节点个数
size_t TreeSize(TreeNode* root)
{
    // 空树
    if (NULL == root)
        return 0;
    // 返回 1 + 左右子树节点个数
    return 1 + TreeSize(root->left) + TreeSize(root->right);
}

// 获得二叉树中序遍历
void GetInOrder(TreeNode* root, int* arr, int* pi)
{
    // 空树
    if (NULL == root)
        return;
    // 左子树
    GetInOrder(root->left, arr, pi);
    // 记录根节点
    arr[*pi] = root->val;
    ++*pi;
    // 右子树
    GetInOrder(root->right, arr, pi);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    // 获得节点个数
    size_t n = TreeSize(root);
    *returnSize = n;
    // 开辟空间
    int* arr = (int*)malloc(sizeof(int)*n);
    // 获得中序遍历
    int i = 0;
    GetInOrder(root, arr, &i);
    // 返回
    return arr;
}

6. 二叉树的后序遍历

题目OJ链接： link

代码如下：

typedef struct TreeNode TreeNode;

// 返回二叉树节点个数
size_t TreeSize(TreeNode* root)
{
    // 空树
    if (NULL == root)
        return 0;
    // 返回 1 + 左右子树节点个数
    return 1 + TreeSize(root->left) + TreeSize(root->right);
}

// 返回二叉树的后序遍历
void GetPostOrder(TreeNode* root, int* arr, int* pi)
{
    // 空树
    if (NULL == root)
        return;
    // 左子树
    GetPostOrder(root->left, arr, pi);
    // 右子树
    GetPostOrder(root->right, arr, pi);
    // 记录根节点
    arr[*pi] = root->val;
    ++*pi;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    // 获得节点个数
    size_t n = TreeSize(root);
    *returnSize = n;
    // 开辟对应空间
    int* arr = (int*)malloc(sizeof(int)*n);
    // 获得中序遍历
    int i = 0;
    GetPostOrder(root, arr, &i);
    // 返回
    return arr;
}

7. 另一颗树的子树

题目描述： 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1：
在这里插入图片描述
输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

示例 2：
在这里插入图片描述
输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

提示：

root 树上的节点数量范围是 [1, 2000]
subRoot 树上的节点数量范围是 [1, 1000]
-10⁴ <= root.val <= 10⁴
-10⁴ <= subRoot.val <= 10⁴

题目OJ链接： link

解题思路： 把当前数与之比较，不相同则比较子树，子树按照这个方法继续比较，直到空树。其中有一颗树与之相同就返回 false。

代码如下：

typedef struct TreeNode TreeNode;

// 判断两棵树是否相同
bool isSameTree(TreeNode* root1, TreeNode* root2)
{
    // 都是空树
    if (NULL == root1 && NULL == root2)
        return true;
    // 有一颗空树
    if (NULL == root1 || NULL == root2)
        return false;
    // 值不相同
    if (root1->val != root2->val)
        return false;
    // 左右子树比较
    return isSameTree(root1->left, root2->left)
        && isSameTree(root1->right, root2->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
    // 空树
    if (NULL == root)
        return false;
    // 当前树判断
    if (isSameTree(root, subRoot))
        return true;
    // 左右子树判断
    return isSubtree(root->left, subRoot)
        || isSubtree(root->right, subRoot);
}

8. 通过前序遍历返回中序遍历

题目描述：
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入描述：
输入包括1行字符串，长度不超过100。

输出描述：
可能有多组测试数据，对于每组数据，输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。每个输出结果占一行。

示例1
输入：
abc##de#g##f###
输出：
c b e g d f a

题目OJ链接： link

解题思路： 首先根据前序遍历构建出这颗二叉树，先构建根节点然后构建左子树，再构建右子树，如此往复，直到空树。再通过构建的二叉树返回其中序遍历。

代码如下：

#include <stdio.h>
#include <stdlib.h>

// 类型声明
typedef char DataType;

// 二叉树节点声明
typedef struct TreeNode
{
    DataType val;
    struct TreeNode* left;
    struct TreeNode* right;
}TreeNode;

// 构建二叉树
TreeNode* CreateTree(char* tmp, int* pi)
{
    // 空树
    if ('#' == tmp[*pi])
    {
        ++(*pi);
        return NULL;
    }
    // 构建根节点
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = tmp[*pi];
    ++(*pi);
    // 构建左右子树
    root->left = CreateTree(tmp, pi);
    root->right = CreateTree(tmp, pi);
    // 返回根节点
    return root;
}

// 中序遍历
void InOrder(TreeNode* root)
{
    // 空树
    if (NULL == root)
        return;
    // 左子树
    InOrder(root->left);
    // 打印根节点
    printf("%c ", root->val);
    // 右子树
    InOrder(root->right);
}

int main() {
    
    // 所需变量
    char tmp[101];
    // 输入
    while (scanf("%s", tmp) != EOF)
    {
        // 构建二叉树
        int i = 0;
        TreeNode* root = CreateTree(tmp, &i);
        // 中序遍历
        InOrder(root);
    }

    return 0;
}

原文地址：https://blog.csdn.net/weixin_70742989/article/details/143699742

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：MySQL Workbench导入数据比mysql命令行慢
下一篇：【redis】—— 环境搭建教程

百度世界大会2024，当应用遇上AI，未来已来
科技更应该服务生活，期待AI技术在更多领域的应用和突破。无论是工作、生活还是娱乐，AI都将为我们带来更加便捷、高效和有趣的体验。
阅读更多2024-11-14
期权懂|交易股票期权该怎么操作？又该如何开户？
期权小懂每日分享期权知识，帮助期权新手及时有效地掌握即市趋势与新资讯！
阅读更多2024-11-14
Blender发布新风格演示视频《Project Gold》
Blender在本月初发布了一条全新风格的演示视频《Project Gold》，短片不同于传统的真实感3D视频，更类似于手绘风格。做为云渲染行业资深平台，已全面支持Blender的云渲染，服务器资源十
阅读更多2024-11-14
JavaScript 原型链的工作原理及如何实现继承
每个 JavaScript 对象在创建时都会拥有一个内部链接，指向另一个对象（称为原型对象）。这个原型对象包含了该对象可以继承的属性和方法。原型的存在使得对象可以共享一些通用的行为。在 JavaScr
阅读更多2024-11-14
如何有效进行谷歌SEO外链建设？
如果你有资源，可以搭建上百甚至上千个网站，用来发布外链，这样就能提升外链的相关性和质量。毕竟，只为了提升一个网站的SEO表现，去维护大量外链站点，并不是每家公司都能负担得起的。所以，很多企业会选择我们
阅读更多2024-11-14
SQL 分组查询中的非聚合列要求及实例解析
聚合列：指的是在SELECT语句中通过聚合函数（如SUM()AVG()MAX()MIN()COUNT()等）计算出的列。它们通常是针对分组数据进行的汇总统计，例如求某个分组中的所有值的和、平均值等。非
阅读更多2024-11-14
地理信息科学专业想搞GIS开发：学前端还是后端？
这就是GIS专业人才的优势所在，他们不仅懂得背后的原理，还懂得如何应用，所以在这个领域找到一份工作是完全可行的。谈到三维GIS领域，不得不说，这个领域的真正主导是计算机图形学和数学，GIS只是其中的一
阅读更多2024-11-14
搭建深度学习开发环境
搭建深度学习开发环境步骤
阅读更多2024-11-14
Flutter：Dio下载文件到本地
使用三方库Dio，完成文件下载
阅读更多2024-11-14
【JAVA毕业设计】基于Vue和SpringBoot的周边产品销售网站
周边产品销售网站是一个B/S模式系统，采用Spring Boot框架作为后台开发技术，前端框架是VUE，MYSQL数据库设计开发，充分保证系统的稳定性。系统具有界面清晰、操作简单，功能齐全的特点，使得
阅读更多2024-11-14

二叉树面试题（C 语言）

目录

1. 单值二叉树

2. 相同的树

3. 对称二叉树

4. 二叉树的前序遍历

5. 二叉树的中序遍历

6. 二叉树的后序遍历

7. 另一颗树的子树

8. 通过前序遍历返回中序遍历

相关文章