[PYTHON] Lassen Sie Code Tag 37 ab Null "105. Konstruieren Sie einen Binärbaum aus Vorbestellung und Inorder Traversal"

Überblick

Es scheint, dass Codierungstests in Ingenieurinterviews im Ausland durchgeführt werden, und in vielen Fällen besteht die Hauptsache darin, bestimmte Funktionen und Klassen entsprechend dem Thema zu implementieren.

Als Gegenmaßnahme scheint eine Website namens Let Code Maßnahmen zu ergreifen.

Eine Site, die algorithmische Leistung trainiert, die Codierungstests standhält, über die früh gesprochen wird.

Ich denke, es ist besser, die Algorithmuskraft eines Menschen zu haben, also werde ich das Problem unregelmäßig lösen und die Methode, die ich damals dachte, als Memo aufschreiben.

Leetcode

Leet Code-Tabelle ab Null

Letztes Mal Leet Code Day 36 "155. Min Stack" ab Null

Im Moment löse ich das Medium mit den 100 beliebtesten Fragen. Easy wurde gelöst. Wenn Sie interessiert sind, gehen Sie bitte zum Tisch.

Twitter Ich mache es.

Problem

105. Construct Binary Tree from Preorder and Inorder Traversal

Der Schwierigkeitsgrad ist Mittel. Auszug aus den 100 beliebtesten Fragen. Da Easy das letzte Mal gelöst wurde, werde ich ab diesem Zeitpunkt Medium lösen.

Das Problem ist, dass als Struktur des Baums "inorder" und "preorder" als Argumente angegeben werden. Schreiben Sie daher einen Algorithmus, der eine darauf basierende Dichotomie erstellt.

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

    3
   / \
  9  20
    /  \
   15   7

Lösung

# 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.

Ich habe es rekursiv gelöst. Da der Stammteil von TreeNode fest ist, habe ich ihn zuerst zugewiesen und dann "Tree" in links und rechts unterteilt und ihn weiterhin rekursiv zugewiesen.

Übrigens gab es eine Diskussion, die kürzer geschrieben wurde, also werde ich sie auch hier posten.

# 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.

Einfach zu lesen und schnell ...! Die Person, die diese Antwort veröffentlicht, ist sehr hilfreich, da sie für jede Frage meist prägnanten Code in Python schreibt.

Bis Easy, wenn Sie ein Element verarbeiten könnten, könnten Sie es lösen, aber mit Medium müssen Sie zwei oder mehr Elemente gut verarbeiten. Ich muss härter arbeiten.

Ich würde gerne mehr darüber diskutieren, danke.