[PYTHON] Let Code Day45 commençant à zéro "1379. Trouver un nœud correspondant d'un arbre binaire dans un clone de cet arbre"

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 de mettre en œuvre 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 à des 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

Table de codes Leet commençant à zéro

Dernière fois Leet Code Day 44 "543. Diamètre de l'arbre binaire" à partir de zéro

À l'heure actuelle, je donne la priorité au moyen des 100 questions les plus appréciées. Easy a été résolu, donc si vous êtes intéressé, veuillez vous rendre à la table.

Twitter Je le fais.

problème

1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree

Le niveau de difficulté est moyen.

Deux arbres binaires, «original» et «cloné», sont donnés, et une référence à «cible» de «original» est donnée.

L'arbre dupliqué est une copie de l'arborescence d'origine et renvoie une référence au même nœud dans l'arborescence dupliquée. Vous n'êtes pas autorisé à modifier les deux arbres ou la «cible» et la réponse doit être une référence à un nœud dans l'arborescence «clonée».

Suivi: si l'arborescence autorise la répétition des valeurs, résolvez le problème.

Solution

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

class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        if not original:
            return None
        if original == target:
            return cloned
        
        return self.getTargetCopy(original.left,cloned.left,target) or self.getTargetCopy(original.right,cloned.right,target)
# Runtime: 672 ms, faster than 60.93% of Python3 online submissions for Find a Corresponding Node of a Binary Tree in a Clone of That Tree.
# Memory Usage: 23.5 MB, less than 100.00% of Python3 online submissions for Find a Corresponding Node of a Binary Tree in a Clone of That Tree.

Je l'ai résolu comme ci-dessus. Je pensais que c'était une réponse relativement bonne parce que je pouvais l'écrire simplement, mais je n'avais pas beaucoup de vitesse, alors j'ai cherché d'autres réponses.

class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        que = collections.deque([(original, cloned)]) # start at the root
        while que:
            nodeOrig, nodeClon = que.popleft()
            if nodeOrig is target: # if original node is found - cloned node is our answer
                return nodeClon
            if nodeOrig.left:  que.append((nodeOrig.left, nodeClon.left))
            if nodeOrig.right: que.append((nodeOrig.right, nodeClon.right))
# Runtime: 656 ms, faster than 92.51% of Python3 online submissions for Find a Corresponding Node of a Binary Tree in a Clone of That Tree.
# Memory Usage: 23.6 MB, less than 100.00% of Python3 online submissions for Find a Corresponding Node of a Binary Tree in a Clone of That Tree.

https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/discuss/539484/Simple-clean-and-fast-Python-solution-7-lines-beats-92

Cette réponse est écrite en utilisant que, mais elle devrait être facile à comprendre. La vitesse est parfaite, et si vous pouvez apprendre à répondre comme ça et y passer au lieu de forcer le problème dans un type que vous pouvez résoudre, ce sera amusant de résoudre le problème!

Jusqu'à ici pour cette fois. Je vous remercie pour votre travail acharné.