[PYTHON] Let Code Day 37 À partir de zéro "105. Construire un arbre binaire à partir de la précommande et de la traversée en ordre"

Aperçu

Il semble que des tests de codage soient menés à l'étranger lors d'entretiens d'ingénieurs, et dans de nombreux cas, l'essentiel est de mettre en œuvre des fonctions et des classes spécifiques en fonction du thème.

En guise de contre-mesure, il semble qu'un site appelé Let Code prendra des mesures.

Un site qui forme une puissance algorithmique capable de résister à des tests de codage dont on parle très tôt.

Je pense qu'il vaut mieux avoir la puissance de l'algorithme d'un être humain, donc je vais résoudre le problème de manière irrégulière et écrire la méthode que j'ai pensé à ce moment-là sous forme de mémo.

Leetcode

Table de codes Leet commençant à zéro

Dernière fois Leet Code Day 36 "155. Min Stack" à partir de zéro

En ce moment, je résous le support des 100 questions les plus appréciées Easy a été résolu, donc si vous êtes intéressé, veuillez vous rendre à la table.

Twitter Je le fais.

problème

105. Construct Binary Tree from Preorder and Inorder Traversal

Le niveau de difficulté est moyen. Extrait des 100 questions les plus appréciées. Depuis Easy a été résolu la dernière fois, je vais résoudre Medium à partir de ce moment.

Le problème est que ʻinorder et preorder` sont donnés comme arguments en tant que structure de l'arbre, alors écrivez un algorithme qui construit un arbre dichotomisé basé sur eux.

preorder = [3,9,20,15,7] inorder = [9,3,15,20,7] Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder or not inorder:
            return None
        
        preordersIndex = preorder[0]
        Tree = TreeNode(preordersIndex)
        inordersIndex = inorder.index(preordersIndex)
        
        Tree.left = self.buildTree(preorder[1:inordersIndex+1],inorder[:inordersIndex])
        Tree.right = self.buildTree(preorder[inordersIndex+1:],inorder[inordersIndex+1:])
        return Tree
# Runtime: 216 ms, faster than 33.07% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
# Memory Usage: 87.7 MB, less than 13.16% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.

Je l'ai résolu récursivement. Puisque la partie racine de TreeNode est fixe, je l'ai affectée en premier, puis j'ai divisé Tree en gauche et droite et j'ai continué à l'attribuer récursivement.

Soit dit en passant, il y avait une discussion qui a été rédigée plus courte que cela, donc je la posterai ici aussi.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if inorder:
            ind = inorder.index(preorder.pop(0))
            root = TreeNode(inorder[ind])
            root.left = self.buildTree(preorder, inorder[0:ind])
            root.right = self.buildTree(preorder, inorder[ind+1:])
            return root
# Runtime: 164 ms, faster than 49.71% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.
# Memory Usage: 52.2 MB, less than 60.53% of Python3 online submissions for Construct Binary Tree from Preorder and Inorder Traversal.

Facile à lire et rapide ...! La personne qui publie cette réponse est très utile car elle écrit principalement du code concis en Python pour toute question.

Jusqu'à Easy, si vous pouviez traiter un élément, vous pourriez le résoudre, mais avec Medium, vous devez bien traiter deux éléments ou plus. Je dois travailler plus dur.

Je voudrais en savoir plus discuter, merci.