[PYTHON] Lassen Sie Code Day12 von vorne beginnen "617. Zwei binäre Bäume zusammenführen"

Ü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 11 ab Null "1315. Summe der Knoten mit Großeltern mit geradem Wert"

Grundsätzlich möchte ich die einfache Akzeptanz in absteigender Reihenfolge lösen.

Problem

617. Merge Two Binary Trees

Der Schwierigkeitsgrad ist einfach und es gibt viele gute.

Das Problem besteht darin, die Zahlen für jede der beiden angegebenen Dichotomien zu addieren und einen neuen Baum zurückzugeben.

Wie oben erwähnt, wird der Baum, zu dem die numerischen Werte jedes übereinstimmenden Teils hinzugefügt werden, als Ausgabe zurückgegeben.

Lösung

Die Idee ist, den anderen Knoten zurückzugeben, wenn einer der Knoten nicht existiert, "Keine", wenn beide Knoten nicht existieren, und die Zahlen hinzuzufügen, wenn beide Knoten existieren.

Dies ist die, die ich vorerst umfassend geschrieben habe.

# 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 mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        if not t1 and not t2:
            return None
        if not t1:
            return t2
        if not t2:
            return t1
        if t1 and t2:
            ans = TreeNode(t1.val + t2.val)
            ans.left = self.mergeTrees(t1.left,t2.left)
            ans.right = self.mergeTrees(t1.right,t2.right)
            return ans
# Runtime: 92 ms, faster than 63.90% of Python3 online submissions for Merge Two Binary Trees.
# Memory Usage: 15.1 MB, less than 5.72% of Python3 online submissions for Merge Two Binary Trees.

Hier ist eine Umschreibung, um zu versuchen, es ein wenig mehr zu vereinfachen

# 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 mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        if not t1:
            return t2
        if not t2:
            return t1
        ans = TreeNode(t1.val + t2.val)
        ans.left = self.mergeTrees(t1.left,t2.left)
        ans.right = self.mergeTrees(t1.right,t2.right)
        return ans
        
# Runtime: 84 ms, faster than 94.01% of Python3 online submissions for Merge Two Binary Trees.
# Memory Usage: 14.9 MB, less than 5.72% of Python3 online submissions for Merge Two Binary Trees.

Es ist schneller, wenn auch ungleichmäßig.