初阶数据结构--二叉树OJ训练

发布于：2025-04-15 ⋅ 阅读:(16) ⋅ 点赞:(0)

本文内容承接上篇问文章，建议连续阅读。

7. 二叉树OJ训练

7.1 单值二叉树

题目链接：965. 单值二叉树 - 力扣（LeetCode）

7.1.1 代码示例
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
typedef struct TreeNode TreeNode;
bool isUnivalTree(TreeNode* root) 
{
    //节点不存在
    //（1.空树也是单值二叉树 2.已经遍历到叶子结点）
    if(root == NULL)
    {
        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);
}
7.1.2 逻辑详解
  • 单值二叉树：所有结点的值都相同的二叉树即为单值二叉树（空树也是单值二叉树）
  • 判断一棵二叉树是否是单值二叉树步骤：
    • 从根节点开始
      • 若根节点为空，这该二叉树为单值二叉树
      • 若根节点不为空，则与其左右孩子结点的val进行比较
        • 若相同，则继续向下遍历
        • 若不同，则直接返回false
    • 持续递归，将每个节点的val的值均与其左右孩子结点的val值进行比较，看是不是一样
      • 若一样，则继续向下遍历
      • 若不一样，则直接返回false
    • 直到递归到叶子，则开始回退返回true。
      • 因为如果能到达叶子结点则表明前面的比较均已通过，没有返回false。
      • 如果中间有出现某个函数栈帧返回了false，则最终的结果均有**&&**连接，所以也会输出false。

7.2 相同的树

题目链接：100. 相同的树 - 力扣（LeetCode）

7.2.1 代码示例
/**
 * 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.根结点均为空树 2.已经遍历到叶子结点
    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);
}
7.2.2 逻辑详解
  • 相同的树：要求两个二叉树的结构相同，并且每个对应结点的值是相同的。
  • 判断两个二叉树是不是相同的树的步骤：
    • 先从根结点开始
      • 若两个二叉树均为空，则为相同的树，返回true
      • 若其中一个为空树，则因为结构不同，不为相同的树，所以返回false
      • 若根节点均不为空，则开始比较两个二叉树的值
        • 若不同，则返回false
        • 若相同，则开始进入递归遍历程序，开始继续向下递归
    • 开始持续递归，对两个二叉树的对应位置的每个结点都进行比较
      • 只要存在值不同的就返回false
      • 如果值相同，则继续向下遍历
    • 直到递归到叶子结点，则开始回退返回true
      • 如果可以到达叶子结点，说明前面的比较已经顺利通过，没有返回false
      • 如果中间有出现某个函数栈帧返回了false，则最终的结果均有**&&**连接，所以也会输出false。
7.2.3 补充练习

题目链接：101. 对称二叉树 - 力扣（LeetCode）

7.2.3.1 代码示例
/**
 * 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.根结点均为空树 2.已经遍历到叶子结点
    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(TreeNode* root) 
{
    return isSameTree(root->left, root->right);
}
7.2.3.2 逻辑详解

此题在上题比较两种二叉树是不是相同的树的基础上变化而来，从代码中也可以看出，新的函数isSymmetric仅仅是调用了isSameTree，并修改了其中的一点逻辑。

  • 对称二叉树：这里指的是二叉树的左半部分和右半部分镜像对称

    在这里插入图片描述

  • 判断一个二叉树是不是对称二叉树的步骤：

    • 在上一题判断两个二叉树是不是相同二叉树的基础上，将根节点的左孩子节点和右孩子结点分别作为参数传进函数isSameTree中，开始遍历比较

    • 但是其中的递归遍历的逻辑需要更改，因为对称二叉树呈镜像对称，所以在最后的return递归语句中，需要将参数的位置发生互换

      return isSameTree(p->left, q->right) && isSameTree(p->left, q->right)
//改为
return isSameTree(p->left, q->right) && isSameTree(p->right, q->left)

    • 再在新函数isSymmetric中调用即可。

7.3 另一棵数的子树

题目链接：572. 另一棵树的子树 - 力扣（LeetCode）

7.3.1 代码示例
/**
 * 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.根结点均为空树 2.已经遍历到叶子结点
    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(TreeNode* root, TreeNode* subRoot) 
{
    if(root == NULL)
    {
        return false;
    }
    //root和subRoot是相同的树
    if(isSameTree(root, subRoot))
    {
        return true;
    }    
    //root和subRoot不是相同的树，但是subRoot仍有可能是root的子树
    //递归遍历比较
    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
7.3.2 逻辑详解

  • 判断 subRoot 是否是二叉树 root 的子树，即检验 root 中是否包含和 subRoot 具有相同结构和结点值的子树，其中 root 和 subRoot 均为非空二叉树。

  • 如下图，subRoot就是root的一个子树

    在这里插入图片描述

  • 判断一棵树是不是另一棵树的子树的思路：

    • 此题还是需要借助前面相同的树中的逻辑和代码。
    • 首先有两种特殊情况
      • 一种是root为空树，因为空树没有子树，所以直接返回false
      • 一种是root和subRoot为相同的树，直接返回true
    • 剩下的普遍情况，就是依靠递归遍历root中的以某个结点为根的子树，与subRoot是否为相同的树。
      • 实际上，当发现 root 中的某一个子树与 subRoot 相匹配时，就不再继续比较其他子树。所以在最后的递归语句中利用||进行连接

    在这里插入图片描述

    就像上图一样，图中只会递归遍历到序号2就结束比较了。

7.4 二叉树遍历

下面三道题目的深度遍历和前文说到的遍历有所不同，前面说到的深度遍历是将一棵二叉树遍历，并将遍历结果打印屏幕上。而下面说到的深度遍历是将一棵二叉树进行遍历，并将遍历结果存储到一个动态开辟的数组中，将数组作为函数返回值进行返回。

7.4.1 前序遍历

题目链接：144. 二叉树的前序遍历 - 力扣（LeetCode）

7.4.1.1 示例代码
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 typedef struct TreeNode TreeNode;

 int TreeSize(TreeNode* root)
 {
    if(root == NULL)
    {
        return 0;
    }
    return 1 + TreeSize(root->left) + TreeSize(root->right);
 }

 void _preorderTraversal(TreeNode* root, int* arr, int* pi)
 {
    if(root == NULL)
    {
        return;
    }
    //根 左 右
    arr[(*pi)++] = root->val;
    _preorderTraversal(root->left, arr, pi);
    _preorderTraversal(root->right, arr, pi);
 }

int* preorderTraversal(struct TreeNode* root, int* returnSize) 
{
    //第一步：先求出二叉树节点的个数
    *returnSize = TreeSize(root);
    //第二步：动态申请内容--arr的大小
    int* returnArr = (int*)malloc(sizeof(int*)*(*returnSize));

    int i = 0;
    _preorderTraversal(root, returnArr, &i);

    return returnArr;
}
7.4.1.2 逻辑详解

  • **整体分析：**在主函数preorderTraversal中，需要实现对二叉树的遍历，并将结点数据存在动态申请的数组returnArr中，之后再递归遍历二叉树，将每个节点的数据放进数组returnArr中，再将其作为返回值返回即可。

  • 确定数组大小：首先，因为需要动态开辟空间，就需要先利用函数TreeSize遍历二叉树获得树中的节点个数，并将返回值存在returnSize，之后便利用求得的二叉树节点个数配合malloc开辟空间并将地址赋给returnArr。

  • 递归结点：后面，可以开始递归遍历二叉树中的节点，因为这里的主函数predorderTraversal前面涉及求二叉树结点和动态开辟空间等语句，所以无法直接递归此函数，所以再创建一个子函数_predorderTraversal，用于递归遍历，这个子函数的逻辑就和前面介绍前序遍历一样，只是将printf("%d ", root->data)改为arr[*(*pi)++] = root->val即可。

  • 子函数参数的传值和传址调用：子函数因为需要不断递归二叉树，并将结点的数值存进数组arr（形参）中去，这其中涉及数组下标的移动问题，因为递归的时候会循环调用子函数_predorderTraversal，如果是传值调用，每次i的值都是一开始传进去的i+1的值，无法实现下标一边递归一边后移的操作，所以这里需要对i进行传址调用。本质还是，在函数中需要对参数内的值进行操作和改变的时候就需要传地址。

  • 补充：空间的释放：这里动态申请了一段连续的空间，所以在释放的时候只需要传数组的首元素地址给free释放一次即可。

7.4.2 中序遍历
7.4.2.1 示例代码
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 typedef struct TreeNode TreeNode;

 int TreeSize(TreeNode* root)
 {
    if(root == NULL)
    {
        return 0;
    }
    return 1 + TreeSize(root->left) + TreeSize(root->right);
 }

 void _inorderTraversal(TreeNode* root, int* arr, int* pi)
 {
    if(root == NULL)
    {
        return;
    }
    //左 根 右
    _inorderTraversal(root->left, arr, pi);
    arr[(*pi)++] = root->val;
    _inorderTraversal(root->right, arr, pi);
 }

int* inorderTraversal(struct TreeNode* root, int* returnSize) 
{
    //第一步：先求出二叉树节点的个数
    *returnSize = TreeSize(root);
    //第二步：动态申请内容--arr的大小
    int* returnArr = (int*)malloc(sizeof(int*)*(*returnSize));

    int i = 0;
    _inorderTraversal(root, returnArr, &i);

    return returnArr;
}
7.4.2.2 逻辑详解

这里的逻辑与上述前序遍历一样，只是在递归的时候存入数据的语句位置，和前文实现中序遍历的printf语句的位置一样，发生了变换。

7.4.3 后序遍历
7.4.3.1 示例代码
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 typedef struct TreeNode TreeNode;

 int TreeSize(TreeNode* root)
 {
    if(root == NULL)
    {
        return 0;
    }
    return 1 + TreeSize(root->left) + TreeSize(root->right);
 }

 void _postorderTraversal(TreeNode* root, int* arr, int* pi)
 {
    if(root == NULL)
    {
        return;
    }
    //左 右 根
    _postorderTraversal(root->left, arr, pi);
    _postorderTraversal(root->right, arr, pi);
    arr[(*pi)++] = root->val;
 }

int* postorderTraversal(struct TreeNode* root, int* returnSize) 
{
    //第一步：先求出二叉树节点的个数
    *returnSize = TreeSize(root);
    //第二步：动态申请内容--arr的大小
    int* returnArr = (int*)malloc(sizeof(int*)*(*returnSize));

    int i = 0;
    _postorderTraversal(root, returnArr, &i);

    return returnArr;
}
7.4.3.2 逻辑详解

这里的逻辑与上述前序遍历一样，只是在递归的时候存入数据的语句位置，和前文实现中序遍历的printf语句的位置一样，发生了变换。

7.5 二叉树的构建及遍历

题目链接：二叉树遍历_牛客题霸_牛客网

7.5.1 题目简述

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

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

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

7.5.2 代码示例
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//定义一个二叉树结点结构
typedef struct BinaryTreeNode
{
    char data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
}BTNode;

//创建一个二叉树节点
BTNode* buyNode(char x)
{
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
    newnode->data = x;
    newnode->left = newnode->right = NULL;

    return newnode;
}

//前序遍历创建一个二叉树（重点！！！）
BTNode* creatTree(char* arr, int* pi)
{
    if (arr[*pi] == '#') 
    {   
        (*pi)++;
        return NULL;
    }
    BTNode* root = buyNode(arr[(*pi)++]);
    //递归创建
    root->left = creatTree(arr, pi);
    root->right = creatTree(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 = creatTree(arr, &i);
    //输出二叉树的中序遍历
    InOrder(root);

    return 0;
}
7.5.3 逻辑详解

此题的难点主要在于如何根据给的字符串数组创建一个二叉树，

**思路：**根据前序遍历字符串数组，可以清晰的画出二叉树，可以得出其中的规律

  • 如果该字符不是**#**，则先以该字符为结点值构建二叉树结点，再循环递归其左子树和右子树
  • 如果该字符是**#，则直接返回到其父结点**位置，不构建新结点
//前序遍历创建一个二叉树（重点！！！）
BTNode* creatTree(char* arr, int* pi)
{
    if (arr[*pi] == '#') 
    {   
        (*pi)++;
        return NULL;
    }
    BTNode* root = buyNode(arr[(*pi)++]);
    //递归创建
    root->left = creatTree(arr, pi);
    root->right = creatTree(arr, pi);

    return root;
}

详解creatTree

  • 函数参数：
    • char* arr：用户输入的字符串数组
    • int* pi：数组下标（这里使用传址调用）
  • 递归停止条件：
    • 当在字符串数组遇到#时，则跳出递归，并且数组下标后移。
  • 循环递归：
    • 根据前文的前序递归的结构，只需要改变对数据的操作即可，这里将printf("%d ", root->data)改为 BTNode* root = buyNode(arr[(*pi)++])实现了二叉树的构建。
  • 构建好二叉树之后，使用中序遍历打印二叉树的数据即可。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布