[PYTHON] Soit Code Day4 à partir de zéro "938. Range Sum of BST"

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 d'implémenter 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 aux 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

En gros, je voudrais résoudre l'acceptation facile par ordre décroissant.

Dernière fois Leet Code Day3 à partir de zéro "1313. Decompress Run-Length Encoded List"

problème

938. Range Sum of BST

BST est un arbre de recherche binaire.

Je pense que certaines personnes ne connaissent pas le concept de l'arbre ou il est ambigu, donc pour l'expliquer brièvement, l'arbre crée une structure hiérarchique dans laquelle plusieurs nœuds enfants sont suspendus sous une «racine» comme indiqué ci-dessous. C'est l'une des idées de la structure de données qui existe. Le nœud terminal qui n'a pas d'enfants est appelé une feuille.

スクリーンショット 2020-04-27 1.42.37.png

Il est exécuté dans le processus d'accès aux données correspondantes depuis la racine via le nœud intermédiaire. De plus, en construisant un arbre basé sur certaines règles, il est possible de donner au nœud intermédiaire le rôle d'index, et il est possible de rationaliser l'accès à des éléments spécifiques.

En tant que méthode de mise en œuvre, un tableau ou des cellules connectées par des pointeurs peuvent être envisagées, mais en général, des cellules connectées par des pointeurs sont utilisées afin de répondre aux changements du nombre d'éléments.

Imaginez l'arbre de dichotomie suivant mentionné dans ce problème.

スクリーンショット 2020-04-27 1.59.14.png

Comme vous pouvez le voir immédiatement, tous les descendants à gauche sont plus petits que le parent à droite et tous les descendants à droite sont plus grands que le nœud parent.

Dans cette situation, lors de la récupération d'un élément, il suffit de juger si les données correspondantes sont plus grandes ou plus petites que l'élément parent dans l'ordre à partir de la racine, et lors de l'ajout d'un élément en plus de cela, le même traitement est effectué pour trouver un nouvel emplacement. L'avantage est qu'il est facile de comprendre s'il faut ajouter un nœud. Lors de la suppression d'un élément, s'il y a un enfant pour remplir le trou après l'avoir supprimé, l'élément est inséré dans le trou tel quel, et s'il y en a deux, le plus petit est inséré dans le trou. Est requis.

Jusqu'à présent, nous avons parlé de la structure des arbres et des arbres dichotomisés. Passons maintenant au problème.

Apparemment, étant donné un arbre de dichotomie nommé root, le but semble être de créer une fonction qui renvoie L et R, la somme de tous les nœuds entre eux, y compris les nœuds gauche et droit. Il existe une restriction selon laquelle toutes les valeurs sont uniques.

J'ai pensé que ce serait plus facile à comprendre si j'y pensais dans un diagramme, alors j'ai fait un diagramme en utilisant l'exemple donné. root = [10,5,15,3,7,null,18], L = 7, R = 15

スクリーンショット 2020-04-27 2.28.33.png

Si vous créez un arbre dichotomisé basé sur les conditions données dans l'exemple 1, il ressemblera à ceci, et les sommes obtenues ici sont L = 7 et R = 15, donc 7 + 10 + 15 = 32. Il convient de noter ici que 5 n'est pas inclus. Certes, si vous suivez les nœuds dans l'ordre, 5 passera, mais comme c'est la somme des valeurs comprises entre L = 7 et R = 15, 5 n'est pas inclus.

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

L'idée est de comparer les valeurs de L et R avec la valeur de node alors qu'il y a une valeur de node donnée, ajouter à la somme si L <= node.value <= R, autrement que L Implémentez une fonction dfs (recherche en profondeur d'abord) qui se déplace vers le nœud de gauche si node.value est grand, et se déplace vers le nœud de droite si node.value est plus petit que R, et l'utilise pour calculer la somme. C'est une méthode d'émission.

La recherche de priorité de profondeur est une recherche récursive de nœud en nœud en fonction de la connexion des arêtes aux enfants et petits-enfants, et est expliquée dans l'article suivant d'une manière très facile à comprendre. [DFS (Depth Priority Search) Super Introduction! ~ Entrée dans le monde des algorithmes graphiques ~ [Partie 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)

De plus, il existe une autre façon de penser qui utilise la récurrence. Un exemple facile à comprendre est [ici](https://leetcode.com/problems/range-sum-of-bst/discuss/192019/JavaPython-3-3-similar-recursive-and-1-iterative-methods-w- commentaire et 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.

Ce problème est très facile à considérer comme un exemple de structure arborescente, d'arbre de dichotomie et de dfs, je vous recommande donc de l'essayer.

Recommended Posts

Soit Code Day4 à partir de zéro "938. Range Sum of BST"
Soit Code Day75 à partir de zéro "15.3 Sum"
Let Code Day 39 "494. Target Sum" à partir de zéro
Let Code Day 33 "1. Two Sum" à partir de zéro
Let Code Day8 À partir de zéro "1302. Somme des feuilles les plus profondes"
Let Code Day 32 "437. Path Sum III" à partir de zéro
Let Code Day 29 "46. Permutations" à partir de zéro
Soit Code Day 65 "560. Subarray Sum Equals K" à partir de zéro
Let Code Day 27 "101. Symmetric Tree" à partir de zéro
Let Code Day 41 "394. Decode String" à partir de zéro
Let Code Day56 À partir de zéro "5453. Somme exécutée de 1d Array"
Let Code Day 25 "70. Grimper les escaliers" à partir de zéro
Laissez Code Day69 à partir de zéro "279. Perfect Squares"
Laissez Code Day85 à partir de zéro "6. Conversion en zigzag"
Let Code Day 88 "139. Word Break" à partir de zéro
Let Code Day 28 "198. House Robber" à partir de zéro
Let Code Day 36 "155. Min Stack" à partir de zéro
Let Code Day 17 "169. Majority Element" à partir de zéro
Let Code Day 23 "226. Invert Binary Tree" en partant de zéro
Soit Code Jour 22 à partir de zéro "141. Cycle de liste liée"
Let Code Day 30 à partir de zéro "234. Palindrome Linked List"
Soit Code Day68 à partir de zéro "709. To Lower Case"
Soit Code Day 44 "543. Diamètre de l'arbre binaire" à partir de zéro
Let Code Day 26 à partir de zéro "94. Traversée en ordre de l'arbre binaire"
Soit Code Day 46 à partir de zéro "406. Reconstruction de file d'attente par hauteur"
Let Code Day 31 "581. Le sous-tableau continu non trié le plus court" à partir de zéro
Let Code Day 38 à partir de zéro "208. Implémenter Trie (Prefix Tree)"
Soit Code Day3 à partir de zéro "1313. Decompress Run-Length Encoded List"
Soit Code Day87 à partir de zéro "1512. Nombre de bonnes paires"
Let Code Day7 À partir de zéro "104. Profondeur maximale de l'arbre binaire"
Soit Code Day92 à partir de zéro "4. Médiane de deux tableaux triés"
Let Code Day 77 "1502. Peut faire une progression arithmétique à partir de la séquence" à partir de zéro
Soit Code Jour 76 à partir de zéro "3. Sous-chaîne la plus longue sans caractères répétitifs"
Let Code Day 35 "160. Intersection de deux listes liées" à partir de zéro
Soit Code Day72 à partir de zéro "1498. Nombre de sous-séquences qui satisfont la condition de somme donnée"
Soit Code Day58 à partir de zéro "20. Parenthèses valides"
Soit Code Day16 à partir de zéro "344. Reverse String"
Soit Code Day49 à partir de zéro "1323. Maximum 69 Number"
Let Code Day89 "62. Chemins uniques" à partir de zéro
Let Code Day 55 "22. Générer des parenthèses" à partir de zéro
Let Code table à partir de zéro
Soit Code Day18 à partir de zéro "53. Maximum Subarray"
Let Code Day 13 "338. Comptage des bits" à partir de zéro
Let Code Day71 À partir de zéro "1496. Traversée de chemin"
Let Code Day 61 "7. Integer Integer" à partir de zéro
Let Code Day 82 "392. Is Subsequence" Partant de zéro
Let Code Day51 "647. Sous-chaînes palindromiques" à partir de zéro
Let Code Day 50 "739. Températures quotidiennes" à partir de zéro
Let Code Day 15 "283. Move Zeroes" à partir de zéro
Soit Code Day14 à partir de zéro "136. Numéro unique"
Let Code Day 9 "701. Insérer dans un arbre de recherche binaire" à partir de zéro
Let Code Day 80 "703. Kth plus grand élément d'un flux" à partir de zéro
Let Code Day6 commençant à zéro "1342. Nombre d'étapes pour réduire un nombre à zéro"
Let Code Day 43 à partir de zéro "5. Le plus long substrat palindromique"
Soit Code Day74 à partir de zéro "12. Integer to Roman"
Let Code Day 42 "2. Add Two Numbers" en partant de zéro
Let Code Day57 À partir de zéro "35. Rechercher Insérer la position"
Soit Code Day47 à partir de zéro "14. Préfixe commun le plus long"
Soit Code Day78 à partir de zéro "206. Liste liée inversée"
Let Code Day 90 à partir de zéro "101 1. Capacité à expédier les colis dans les D jours"
Let Code Day10 À partir de zéro "1431. Enfants avec le plus grand nombre de bonbons"