Programmation pour combattre dans le monde - Chapitre 4

tree.py



# -*- coding:utf-8 -*-
import math

    
class TreeNode:
    def __init__(self,data=None,left=None,right=None):
        self.data = data
        self.left = left
        self.right = right
        self.adjacent = [self.left,self.right]
        self.visited = False
        self.next =None
        

class Treeutils:
    def __init__(self):
        self.classes = 0
    def treeappend(self,node,x):
        if node == None:
            return TreeNode(x)
        elif x == node.data:
            return node
        elif x < node.data:
            node.left = self.treeappend(node.left,x)
        else:
            node.right = self.treeappend(node.right,x)
            
        return node
        

    def treecheck(self,node):
        if node == None:
            return 0
        leftheight = self.treecheck(node.left)
        if leftheight == -1:
            return -1
        
        rightheight = self.treecheck(node.right)
        if rightheight == -1:
            return -1
        
        heightdiff = leftheight - rightheight
        
        if math.fabs(heightdiff) > 1:
            return -1
        else:
            return max(leftheight,rightheight) + 1
        
    def isBalanced(self,node):
        if self.treecheck(node) == -1:
            return None
        else:
            return True
        
    def createMinBST(self,arr =[],start = 0,end = 0):
        if end < start:
            return None
        mid = (start + end) / 2
        
        n = TreeNode(arr[int(mid)])
        n.left = self.createMinBST(arr,start,mid -1)
        n.right = self.createMinBST(arr,mid+1,end)
        return n
    
    def create(self,x):
        return self.createMinBST(range(x),0,len(range(x))-1)
    
    def covers(self,root,p):
        if root == None:
            return False
        if root == p:
            return True
        return self.covers(root.left,p) or self.covers(root.right,p)
    
    def commonAncestorHelper(self,root,p,q):
        if root == None:
            return None
        if root == p or root == q:
            return root
        is_p_on_left = self.covers(root.left,p)
        is_q_on_right = self.covers(root.right,q)
        
        if is_p_on_left != is_q_on_right:
            return root
        
        child = is_p_on_left if root.left else root.right
        
        return self.commonAncestorHelper(child,p,q)
    
    def commonAncestor(self,root,p,q):
        if self.covers(root,p) != True or self.covers(root,q) != True:
            return None
        return self.commonAncestorHelper(root,p,q)
            
        
    def containsTree(self,node1,node2):
        if node2 == None:return True
        return self.subTree(node1,node2)
    
    def subTree(self,node1,node2):
        if node1 == None:
            return False
        
        if node1.data ==node2.data:
            if self.matchTree(node1,node2):
                return True
        
        return self.subTree(node1.left,node2) or self.subTree(node1.right,node2)
    
    def matchTree(self,node1,node2):
        if node1 == None and node2 == None:
            return True
        
        if node1 or node2 == None:return False
        
        if node1.data != node2.data:return False
        
        return self.matchTree(node1.left,node2.left) and self.matchTree(node1.right,node2.right)
                

tester Je n'ai pas fait les quatre chapitres. Je le fais, mais ce n'est tout simplement pas répertorié (tremblant) Je ne sais pas si l'arborescence des correspondances fonctionne correctement

Recommended Posts

Programmation pour combattre dans le monde - Chapitre 4
Programmation pour combattre dans le monde ~ 5-1
Programmation pour combattre dans le monde ~ 5-5,5-6
Programmation pour combattre dans le monde ~ 5-2
Fiche d'activité dans le cercle de programmation
"Livre pour former la capacité de programmation à se battre dans le monde" Exemple de réponse de code Python --1.3 URLify
Dans la commande python, python pointe vers python3.8
"Livre pour former la capacité de programmation à se battre dans le monde" Exemple de réponse au code Python - 2,6 fois
Essayez Cython dans les plus brefs délais
"Livre pour former des compétences en programmation pour combattre dans le monde" Exemple de réponse de code Python --2.4 Fractionnement de la liste
"Un livre pour former les compétences de programmation pour combattre dans le monde" Exemple de réponse de code Python --2.7 nœuds d'intersection
"Livre pour former la capacité de programmation à se battre dans le monde" Exemple de réponse au code Python - Matrice de 1,8 "0"
Dans Jupyter, ajoutez IPerl au noyau.
Dessiner des graphiques dans le langage de programmation Julia
Divers commentaires à écrire dans le programme
"Livre pour former la capacité de programmation à se battre dans le monde" Exemple de solution de code Python --1.6 Compression de chaîne de caractères
"Livre pour former la capacité de programmation à se battre dans le monde" Exemple de solution de code Python --1.5 Conversion en une seule fois
"Un livre pour former les compétences de programmation pour combattre dans le monde" Exemple de réponse de code Python --3.1 Trois piles
"Livre pour former des compétences en programmation pour combattre dans le monde" Exemple de solution de code Python - 1.7 Rotation de matrice
"Un livre pour former des compétences en programmation pour combattre dans le monde" Exemple de réponse au code Python --1.4 Séquence de phrases
"Un livre pour former les compétences de programmation pour combattre dans le monde" Exemple de solution de code Python --2.8 Détection de boucle
"Livre pour former les compétences de programmation pour combattre dans le monde" Exemple de réponse de code Python --- Éléments supprimés entre 2.3
"Livre pour former des compétences en programmation pour combattre dans le monde" Exemple de solution de code Python --2.1 Supprimer les éléments en double
Programmation avec Python
"Livre pour former la capacité de programmation à se battre dans le monde" Exemple de réponse de code Python --1.9 Rotation de la chaîne de caractères
"Livre pour former des compétences en programmation pour combattre dans le monde" Exemple de solution de code Python --1.1 Chaîne de caractères en double
Client de streaming Twitter à apprécier dans le terminal
Pour remplacer dynamiquement la méthode suivante en python
Dessinez des graphiques dans Julia ... Laissez les graphiques à Python
Conseils pour rédiger un aplatissement concis en python
Comment obtenir les fichiers dans le dossier [Python]
Connectez-vous avec json en utilisant pygogo.
Je veux afficher la progression en Python!
"Livre pour former la capacité de programmation à se battre dans le monde" Exemple de réponse de code Python --2.2 Renvoyer Kth par l'arrière
Comment récupérer la nième plus grande valeur en Python
J'ai essayé de représenter graphiquement les packages installés en Python
Comment obtenir le nom de la variable lui-même en python
Essayez de résoudre le livre des défis de programmation avec python3
Comment exécuter le module Ansible ajouté dans Ansible Tower
Comment obtenir le nombre de chiffres en Python
Comment connaître le répertoire actuel en Python dans Blender
"Livre pour former la capacité de programmation à se battre dans le monde" Exemple de réponse de code Python --1.2 Compter le nombre des mêmes caractères
Convertissez l'image au format .zip en PDF avec Python
Définissez DateField du formulaire sur type = date dans Django
Comment utiliser la clause exist dans l'ensemble de requêtes Django
Je veux écrire en Python! (3) Utiliser des simulacres
La route vers Pythonista
Programmation Python avec Excel
Comment utiliser le modèle appris dans Lobe en Python
Essayez de déchiffrer les données de connexion stockées dans Firefox
Le robot en ligne le plus simple au monde pour perdre du poids
Comment profiter de Python sur Android !! Programmation en déplacement !!
Ne passez pas self à ProcessPoolExecutor en classe
[Python] Comment afficher les valeurs de liste dans l'ordre
Kaggle Tutorial Le savoir-faire Titanic pour être dans le top 2%
La route vers Djangoist
Pour faire l'équivalent de Ruby ObjectSpace._id2ref en Python
Le langage de programmation que vous souhaitez pouvoir utiliser
Parlez de l'API d'acquisition du temps dans le langage de programmation
Je veux utiliser le jeu de données R avec python
Python Open CV a essayé d'afficher l'image sous forme de texte.