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