3

二叉树练习题_萌新的日常的技术博客_51CTO博客

 2 years ago
source link: https://blog.51cto.com/u_15787387/5690997
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

一、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;
}
二叉树练习题_插入图片_02
主要是分治思想，大事化小，把其化成带有根节点的A
A的左子树，A的右子树 ,再分别判断左子树与右子树的最大深度，
取两者最大值+1即二叉树的最大深度

递归展开图

二叉树练习题_插入图片_03

二、110. 平衡二叉树

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

二叉树练习题_子树_04
/**
 * 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
   &&isBalanced(root->left)
   &&isBalanced(root->right);
}

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

递归展开图

二叉树练习题_二叉树_05
二叉树练习题_子树_06

三、二叉树遍历

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： 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,&i);
    inorder(root);
    return 0;
}

首先就以本题的例子来说明，'#'代表空格
abc##de#g##f###

二叉树练习题_插入图片_07

递归展开图

二叉树练习题_子树_08

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK