二叉树专项练习

lovevivi

发布于 2022-11-10 14:54:08

1490

发布于 2022-11-10 14:54:08

文章被收录于专栏：萌新的日常

一、104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。
示例：给定二叉树 [3,9,20,null,null,15,7]，

返回它的最大深度 3 。

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


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

主要是分治思想，大事化小，把其化成带有根节点的A A的左子树，A的右子树 ,再分别判断左子树与右子树的最大深度，取两者最大值+1即二叉树的最大深度

递归展开图

二、110. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int maxDepth(struct TreeNode* root){
    if(root==NULL)
    {
        return 0;
    }
   int left=maxDepth(root->left);
   int right=maxDepth(root->right);
   return left>right?left+1:right+1;
}
bool isBalanced(struct TreeNode* root){
   if(root==NULL)
   {
       return true;
   }
   int leftdepth=maxDepth(root->left);
   int rightdepth=maxDepth(root->right);
   return abs(leftdepth-rightdepth)<2
   &amp;&amp;isBalanced(root->left)
   &amp;&amp;isBalanced(root->right);
}

本题也是使用了二叉树的最大深度，我本来的想法是跟上题差不多求根节点的左子树和根节点的右子树，但是后来我发现忽略了每个节点都要差一这个条件。这道题也是使用了c语言求绝对值所使用的 abs 只有满足该点的左子树和左子树相差小于2并且左子树与右子树本身递归也相差小于2才成立

递归展开图

三、二叉树遍历

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
输入描述: 输入包括1行字符串，长度不超过100。输出描述: 可能有多组测试数据，对于每组数据，输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。每个输出结果占一行。
示例1 输入 abc##de#g##f### 输出 c b e g d f a

#include<stdio.h>
#include<stdlib.h>
typedef struct treenode
{
    char val;
    struct treenode*left;
    struct treenode*right;
}BTnode;
BTnode*tree(char *a,int*i)//创建二叉树
{
    if(a[*i]=='#')
    {
        (*i)++;//为#看作一个空格 ，跳过
        return NULL;
    }
    BTnode*root=(BTnode*)malloc(sizeof(BTnode));//在函数内创建二叉树结构体类型，最大程度上知道了二叉树的节点个数
        root->val=a[*i];
        (*i)++;//这里不要忘记将i+1 ，将a的值指向下一个
        root->left=tree(a,i);//两次循环调用
        root->right=tree(a,i);
    return root;//返回结构体指针，可以找到二叉树
}
void inorder(BTnode*root)//二叉树的中序遍历 递归
{
    if(root==NULL)
    {
        return ;
    }
    inorder(root->left);//左子树
    printf("%c ",root->val);//根
    inorder(root->right);//右子树
}
int main()
{
    char arr[40]={0};
    scanf("%s",arr);
    int i=0;//这里我们想要通过函数得到i的值 ，需要传址调用
    BTnode*root=tree(arr,&amp;i);
    inorder(root);
    return 0;
}