《数据结构初阶》【二叉树 精选9道OJ练习】

往期《数据结构初阶》回顾：
【时间复杂度 + 空间复杂度】
【顺序表 + 单链表 + 双向链表】
【顺序表/链表 精选15道OJ练习】
【顺序栈 + 链式队列 + 循环队列】
【链式二叉树】
【堆 + 堆排序 + TOP-K】

前言：

🌳【二叉树终章试炼】⚔️
二叉树初阶的学习到这里就已经算是结束了，马上就要到了大家期待的排序算法的学习了，站在数据结构新手村的岔路口，前方排序算法的宝藏山洞泛着金光✨——但宝子们先别急！你腰间那柄二叉树锻造的算法之剑，还差最后9次淬火才能开刃！🗡️
其实是：博主还没有将排序算法的博客写出来

二叉树的OJ练习

144. 二叉树的前序遍历

题目介绍

方法一：

/**
 * 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().
 */

//1.实现：“二叉树的求树中节点的总个数”操作
int BTSize(struct TreeNode*root)
{
    //1.处理：“空树 + 遍历到空节点”的情况
    if(root==NULL) return 0;
    
    //2.递归计算二叉树中节点的个数
    return BTSize(root->left)+BTSize(root->right)+1;
}

//2.实现：“二叉树的前序遍历”操作
void PrevOrder(struct TreeNode*root,int*arr,int* pi)
{
    //1.处理：“空树 + 空节点”的情况
    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.进行前序遍历将遍历的次数存储到数组中


    //1.动态开辟数组空间
    *returnSize=BTSize(root);
    int* arr=(int*)malloc(*returnSize*sizeof(int));
    int i=0;

    //2.先序序列填充数组
    PrevOrder(root,arr,&i);

    return arr;
}

104. 二叉树的最大深度

题目介绍

方法一：

/**
 * Definition for a binary tree node.
 * struct TreeNode 
 * {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

 //问题的本质：二叉树的最大深度=fmax(左子树的深度,右子树的深度);
int maxDepth(struct TreeNode* root) 
{
    //1. 处理：空树的情况
    if(root==NULL)  return 0;


    return fmax(maxDepth(root->left),maxDepth(root->right))+1;
}

965. 单值二叉树

题目介绍

方法一：

/**
 * Definition for a binary tree node.
 * struct TreeNode 
 * {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

bool isUnivalTree(struct TreeNode* root) 
{
    //1.处理：空树的情况
    if(root==NULL) return true;

    //2.使用if判断：如果双亲节点的值不等于孩子节点的值
    if(root->left&&root->left->val!=root->val) return false;

    if(root->right&&root->right->val!=root->val) return false;


    //3.1：在左子树中进行递归
    bool ret=isUnivalTree(root->left);
    if(!ret) return false;
    //3.2：在右子树中进行递归
    ret=isUnivalTree(root->right);
    if(!ret) return false;

    //4.返回通过所有检测的返回值
    return true;
    
    //注：上面的写法也可以写成下面的更简洁的写法
    //使用递归判断左子树和右子树的节点的情况 （将左子树和右子树进行汇总）
    //return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

100. 相同的树

题目介绍

方法一：

/**
 * Definition for a binary tree node.
 * struct TreeNode 
 * {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{
    //1.处理：两颗树都为空树的情况
    if(p==NULL&&q==NULL) return true;
    //2.处理：其中一颗树为空树的情况
    if(p==NULL||q==NULL) return false;

    //3.使用if判断：如果的两棵树的节点的值不相等
    if(p->val!=q->val) return false;

    //3.递归判断左子树和右子树的所有节点是否相等
    bool ret=isSameTree(p->left,q->left);
    if(!ret) return false; //这里是当我们未遍历完所有的节点时就已经出现了节点不匹配的情况的话，我们就先让递归提前结束

    ret=isSameTree(p->right,q->right);
    if(!ret) return false; 

    return true;
}

101. 对称二叉树

题目介绍

方法一：

/**
 * Definition for a binary tree node.
 * struct TreeNode 
 * {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 

bool _isSymmetric(struct TreeNode* root1,struct TreeNode*root2)
{
    //1.处理：左子树和右子树都为空树的情况
    if(root1==NULL&&root2==NULL)  return true;

    //2.处理：左子树和右子树中有一颗树是空树
    if(root1==NULL||root2==NULL) return false;

    //3.处理：左子树和右子树都不为空树，但是对应位置的节点的值却不相等
    if(root1->val!=root2->val) return false;

    //4.进行递归遍历左子树和右子树中的节点
    //4.1：比较：“左子树的左孩子 and  右子树的右孩子”
    bool ret =_isSymmetric(root1->left,root2->right);
    if(!ret) return false;

    //4.2：比较：“左子树的右孩子 and  右子树的左孩子”
    ret =_isSymmetric(root1->right,root2->left);
    if(!ret) return false;

    return true;
    
    //注意：上面的第四步也可以用下面的这一句代码进行代替
    //return _isSymmetric(root1->left,root2->right)&&_isSymmetric(root1->right,root2->left);
}

bool isSymmetric(struct TreeNode* root) 
{
    //1.确保进行判断的这颗树是一颗合法的树
    if(!root) return false;

    //2.调用子函数解决问题
    return  _isSymmetric(root->left,root->right);
}

572. 另一棵树的子树

题目介绍

方法一：

/**
 * Definition for a binary tree node.
 * struct TreeNode 
 * {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */



bool isSameTree(struct TreeNode*root1,struct TreeNode*root2)
{
    //1.处理：“空树 + 遍历到空节点” 的情况
    if(root1==NULL&&root2==NULL) return true;

    //2.处理：其中一棵树为空树另一棵树不为空树的情况
    if(root1==NULL||root2==NULL) return false;

    //3.处理：两棵树都不为空树但是，但是当前遍历到的节点的值不相等
    if(root1->val!=root2->val) return false;

    //4.进行递归判断两棵树的其他节点
    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）判断两棵二叉树是否相等


    //1.处理：“空树 + 遍历到空节点” 的情况
    if(root==NULL) return false;

    //2.使用if判断：如果我们找到这个节点
    if(isSameTree(root,subRoot)) return true;

    //3.进行递归遍历
    //3.1：递归左子树进行寻找
    bool ret=isSubtree(root->left,subRoot);
    if(ret) return ret;
    //3.2：递归右子树进行寻找
    ret=isSubtree(root->right,subRoot);
    if(ret) return ret;

    return false;
}

KY11 二叉树遍历

题目介绍

开始挑战： KY11 二叉树遍历

方法一：

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

//二叉树的存储结构
typedef struct BinaryTreeNode
{
    int data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
    
}BTNode;

//1.实现：“二叉树的中序遍历”操作
void InOrder(BTNode*root)
{
    //1.处理：“空树 + 空节点”的情况
    if(root==NULL) return;

    //2.递归进行中序遍历
    InOrder(root->left);
    printf("%c ",root->data);
    InOrder(root->right);
}

//2.实现：“根据前序遍历字符串创建出一棵二叉树”
BTNode* BTCreate(char* arr,int* pi)
{
    //1.先处理空节点
    if(arr[*pi]=='#') //注意：这里不要写成if(arr[(*pi)++]==NULL)的形式
    {                 //原因：写成这样无论当前数组中的元素是否为'#'都会使(*pi)++
        (*pi)++;
        return NULL;
    } 

    //2.再处理非空节点
    //2.1：使用malloc为树节点开辟空间
    BTNode* root=(BTNode*)malloc(sizeof(BTNode));

    //2.2：为节点进行赋值
    root->data=arr[*pi];
    (*pi)++;
    //2.3：为节点创建结构
    root->left=BTCreate(arr,pi);
    root->right=BTCreate(arr,pi);


    //3.返回创建出的二叉树的根节点
    return root;
}


int main() 
{
    //1.获取数据
    char arr[100];
    scanf("%s",arr);
    int i=0;


    //2.处理数据
    BTNode*root=BTCreate(arr, &i);

    //3.输出数据：
    InOrder(root);
    return 0;
}

226. 翻转二叉树

题目介绍

方法一：

/**
 * 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) 
{
    //1.处理空树的情况 （同时也是递归结束的条件 ---> 传入参数的空节点的时候，停止递归）
    if(root==NULL) return NULL;

    //2.交换遍历到的节点的左右孩子 
    Swap(&root->left,&root->right);

    //3.递归处理其他的节点
    invertTree(root->left);
    invertTree(root->right);

    //4.将处理后的二叉树的根节点返回
    return root; 
}

110. 平衡二叉树

题目介绍

方法一：

/**
 * Definition for a binary tree node.
 * struct TreeNode 
 * {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

/*--------------实现求一个求树高度的方法--------------*/
int BTHeight(struct TreeNode*root)
{
    //1.处理空树的情况 （同时也是递归结束的条件 ---> 传入参数的空节点的时候，停止递归）
    if(root==NULL) return 0;

    //2.递归处理左子树的情况
    int leftHeight=BTHeight(root->left);
    //3.递归处理右子树的情况
    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);

}