Arbre binaire OJ sujet

Arbre binaire à valeur unique

Comment résoudre le problème

La solution de base est de comparer Valeurs de la racine et des noeuds gauche et droit égal ou non.
En écriture récursive, Conditions de retour ,Si la racine est vide,Renvoie True; Les racines ont été comparées aux enfants de gauche et de droite. , Retourner false si différent . Enfin, deux sous - arbres à gauche et à droite. .

Code

bool isUnivalTree(struct TreeNode* root){
    
    if(root==NULL)
    return true;

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

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

   return isUnivalTree(root->left)&&isUnivalTree(root->right);

}

Profondeur maximale de l'arbre binaire

Description du sujet

Comment résoudre le problème

La hauteur de l'arbre est la plus longue , La hauteur de l'arbre est la hauteur des sous - arbres à gauche et à droite. , Plus la hauteur maximale du sous - arbre 1 C'est la hauteur de l'arbre. . Notez les paramètres de la fonction et s'il y a une valeur de retour lors de l'écriture de la récursion .

Écris d'abord la sortie. , Renvoie lorsque le noeud est vide 0,
Passe.：Comparer la hauteur des sous - arbres gauche et droit
Retour à：Largeur maximale

Code

int maxDepth(struct TreeNode* root){
    
    if(root==NULL)
    return 0;

    int L=maxDepth(root->left)+1;
    int R=maxDepth(root->right)+1;

    return L>R?L:R;
}

Même arbre

Description du sujet

Comment résoudre le problème

Nous prenons la méthode de traversée pré - ordonnée ,Comparez d'abord le noeud racine, Puis comparez les sous - arbres de gauche et de droite .
Seulement les racines., Les arbres de gauche et de droite sont les mêmes avant de revenir. true. Le reste revient. false.

Code

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    
    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);
}

Arbre binaire symétrique

Description du sujet

Comment résoudre le problème

À l'exception du noeud racine,Du sous - arbre gauche Noeuds gauche et droit Avec le Sous - arbre droit Noeud droit - gauche Comparer.
Retour admissibletrue,Sinon, retournez àfalse.

Code

bool isSymmetryTree(struct TreeNode* p, struct TreeNode* q){
    
    if(p==NULL&&q==NULL)
    return true;

    if(p==NULL||q==NULL)
    return false;

    if(p->val!=q->val)
    return false;

    return isSymmetryTree(p->left,q->right)&&isSymmetryTree(p->right,q->left);
}

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

Traversée pré - ordonnée de l'arbre binaire

Description du sujet

Comment résoudre le problème

Trouvez d'abord combien de noeuds il y a , Ensuite, passez à travers ,La traversée pré - ordonnée est la première traversée du noeud racine, Puis traversez les noeuds enfants gauche et droit . Stocker les données dans un tableau lorsque le noeud n'est pas vide .

Code

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

void PreorderTree(struct TreeNode* root,int* a,int* n)
{
    
    if(root==NULL)
    return;
    a[*n]=root->val;
    ++*n;
    PreorderTree(root->left,a,n);
    PreorderTree(root->right,a,n);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    
    *returnSize=TreeSize(root);

    int* arr=(int*)malloc((*returnSize)*sizeof(int));
    int n=0;
    PreorderTree(root,arr,&n);
    return arr;
}

Traversée du milieu de l'arbre binaire

Description du sujet

Code

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

void  inorderTree(struct TreeNode* root,int* a,int* n)
{
    
    if(root==NULL)
    return;
    
    inorderTree(root->left,a,n);
    a[*n]=root->val;
    ++*n;
    inorderTree(root->right,a,n);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    
    *returnSize= TreeSize(root);
    int* arr=(int*)malloc((*returnSize)*sizeof(int));
    int n=0;
     inorderTree(root,arr,&n);
     return arr;
}

Traversée post - ordre de l'arbre binaire

Description du sujet

Code

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

void  postorderTree(struct TreeNode* root,int* a,int* n)
{
    
    if(root==NULL)
    return;
    
   postorderTree(root->left,a,n);
    
    postorderTree(root->right,a,n);
    a[*n]=root->val;
    ++*n;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){
    
    *returnSize= TreeSize(root);
    int* arr=(int*)malloc((*returnSize)*sizeof(int));
    int n=0;
     postorderTree(root,arr,&n);
     return arr;
}

Un enfant d'un autre arbre

Description du sujet

Comment résoudre le problème

TraverséerootArbre,Quandroot Valeur du noeud et subroot Lorsque la valeur du noeud racine est la même , Commencez à les comparer. ,Si c'est le même, retournez àtrue, Sinon, continuez à traverser les sous - arbres gauche et droit. . Le résultat de la traversée des sous - arbres gauche et droit est ||.

Code

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    
    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(struct TreeNode* root, struct TreeNode* subRoot){
    
    if(root==NULL)
    return false;
    if(root->val==subRoot->val)
      if(isSameTree(root,subRoot))
      return true;
    return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
    
}

Arbre binaire traversant

Description du sujet

Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char BTDataType;

typedef struct BinaryTreeNode
{
    
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType data;
}BTNode;
BTNode* BuyNode(char ch)
{
    
    BTNode* newnode=(BTNode*)malloc(sizeof(BTNode));
    newnode->data=ch;
    newnode->left=newnode->right=NULL;
    return newnode;
}


BTNode* CreatTree(char* arr,int n,int* i)
{
    
   if(arr[*i]!='#'&&*i<n)
   {
    
       BTNode* root=BuyNode(arr[*i]);
       ++*i;
       root->left=CreatTree(arr, n, i);
       root->right=CreatTree(arr, n, i);
       return root;
   }
   else
    {
    
       ++*i;
       return NULL;
    }
    
}
void inorderTree(BTNode* root)
{
    
    if(root==NULL)
        return;
    inorderTree(root->left);
    printf("%c ",root->data);
    inorderTree(root->right);
}
int main()
{
    
    char arr[100];
    scanf("%s",arr);
    int len=strlen(arr);
    int i=0;
    BTNode* root=CreatTree(arr,len,&i);
    inorderTree(root);
    return 0;
}