[PYTHON] Lassen Sie Code Day4 von vorne beginnen "938. Range Sum of BST"

Ü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

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

Letztes Mal Leet Code Day3 ab Null "1313. Codierte Liste mit laufender Länge dekomprimieren"

Problem

938. Range Sum of BST

BST ist ein binärer Suchbaum.

Ich denke, dass einige Leute das Konzept des Baums nicht kennen oder es nicht eindeutig ist. Um es kurz zu erklären, erstellt der Baum eine hierarchische Struktur, in der mehrere untergeordnete Knoten unter einer "Wurzel" hängen, wie unten gezeigt. Es ist eine der Ideen der vorhandenen Datenstruktur. Der Endknoten, der keine untergeordneten Knoten hat, wird als Blatt bezeichnet.

Es wird ausgeführt, während über den Zwischenknoten von der Wurzel aus auf die entsprechenden Daten zugegriffen wird. Durch Erstellen eines Baums basierend auf bestimmten Regeln ist es außerdem möglich, dem Zwischenknoten die Rolle eines Index zuzuweisen und den Zugriff auf bestimmte Elemente zu optimieren.

Als Implementierungsmethode können ein Array oder Zellen, die durch Zeiger verbunden sind, betrachtet werden, aber im Allgemeinen werden Zellen, die durch Zeiger verbunden sind, verwendet, um auf Änderungen in der Anzahl von Elementen zu reagieren.

Stellen Sie sich den folgenden Dichotomiebaum vor, der in diesem Problem erwähnt wird.

Wie Sie sofort sehen können, sind alle Nachkommen links kleiner als die Eltern rechts und alle Nachkommen rechts größer als der Elternknoten.

In dieser Situation ist es beim Abrufen eines Elements ausreichend zu beurteilen, ob die entsprechenden Daten in der Reihenfolge vom Stamm aus größer oder kleiner als das übergeordnete Element sind, und wenn ein Element darüber hinzugefügt wird, wird dieselbe Verarbeitung durchgeführt, um einen neuen Ort zu finden. Der Vorteil ist, dass leicht zu verstehen ist, ob ein Knoten hinzugefügt werden soll. Wenn beim Löschen eines Elements ein untergeordnetes Element vorhanden ist, um das Loch nach dem Löschen zu füllen, wird das Element unverändert in das Loch eingefügt, und wenn zwei vorhanden sind, wird das kleinere Element in das Loch eingefügt. Wird benötigt.

Bisher haben wir über die Struktur von Bäumen und dichotomisierten Bäumen gesprochen. Kommen wir nun zum Problem.

Bei einem Dichotomiebaum mit dem Namen "root" scheint das Ziel darin zu bestehen, eine Funktion zu erstellen, die L und R zurückgibt, die Summe aller Knoten zwischen ihnen, einschließlich des linken und rechten Knotens. Es gibt eine Einschränkung, dass alle Werte eindeutig sind.

Ich dachte, es wäre einfacher zu verstehen, wenn ich in einem Diagramm darüber nachdenken würde, also habe ich anhand des angegebenen Beispiels ein Diagramm erstellt. root = [10,5,15,3,7,null,18], L = 7, R = 15

Wenn Sie einen dichotomisierten Baum basierend auf den in Beispiel 1 angegebenen Bedingungen erstellen, sieht er folgendermaßen aus, und die hier erhaltenen Summen sind L = 7 und R = 15, also 7 + 10 + 15 = 32. Es ist hier zu beachten, dass 5 nicht enthalten ist. Wenn Sie den Knoten in der richtigen Reihenfolge folgen, wird zwar 5 übergeben, aber da es sich um die Summe der Werte handelt, die zwischen L = 7 und R = 15 enthalten sind, ist 5 nicht enthalten.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
        def dfs(node):
            if node:
                if L <= node.val <= R:
                    self.ans += node.val
                if L < node.val:
                    dfs(node.left)
                if R > node.val:
                    dfs(node.right)
        self.ans = 0
        dfs(root)
        return self.ans
# Runtime: 224 ms, faster than 82.22% of Python3 online submissions for Range Sum of BST.
# Memory Usage: 21.9 MB, less than 7.92% of Python3 online submissions for Range Sum of BST.

Die Idee ist, die Werte von L und R mit dem Wert des Knotens zu vergleichen, während es einen gegebenen Wert des Knotens gibt, und zur Summe zu addieren, wenn L <= Knotenwert <= R, anders als L. Implementieren Sie eine Funktion dfs (Tiefensuche), die sich zum linken Knoten bewegt, wenn node.value groß ist, und zum rechten Knoten, wenn node.value kleiner als R ist, und berechnen Sie damit die Summe. Es ist eine Ausstellungsmethode.

Die Suche mit Tiefenpriorität ist eine rekursive Suche von Knoten zu Knoten gemäß der Verbindung von Kanten mit Kindern und Enkelkindern und wird im folgenden Artikel auf sehr leicht verständliche Weise erläutert. [DFS (Depth Priority Search) Super Einführung! ~ Einstieg in die Welt der Graph-Algorithmen ~ [Teil 1]](https://qiita.com/drken/items/4a7869c5e304883f539b#3-%E6%B7%B1%E3%81%95%E5%84%AA% E5% 85% 88% E6% 8E% A2% E7% B4% A2-dfs-% E3% 81% A8% E5% B9% 85% E5% 84% AA% E5% 85% 88% E6% 8E% A2 % E7% B4% A2-bfs)

Darüber hinaus gibt es eine andere Denkweise, die Wiederholung verwendet. Ein leicht verständliches Beispiel ist [hier](https://leetcode.com/problems/range-sum-of-bst/discuss/192019/JavaPython-3-3-similar-recursive-and-1-iterative-methods-w- Kommentar und Analyse.).

def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
        if not root:
            return 0
        elif root.val < L:
            return self.rangeSumBST(root.right, L, R)
        elif root.val > R:
            return self.rangeSumBST(root.left, L, R)
        return root.val + self.rangeSumBST(root.left, L, R) + self.rangeSumBST(root.right, L, R)
# Runtime: 244 ms, faster than 47.97% of Python3 online submissions for Range Sum of BST.
# Memory Usage: 22.1 MB, less than 5.94% of Python3 online submissions for Range Sum of BST.

Dieses Problem ist sehr einfach als Beispiel für Baumstruktur, Dichotomiebaum und dfs zu verstehen. Ich empfehle Ihnen daher, es auszuprobieren.