[PYTHON] Let Code Day45 Starting from Zero "1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree"

Overview

It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.

As a countermeasure, it seems that a site called Let Code will take measures.

A site that trains algorithmic power that can withstand coding tests that are often done in the home.

I think it's better to have the algorithm power of a human being, so I'll solve the problem irregularly and write down the method I thought at that time as a memo.

Leetcode

Leet Code Table of Contents Starting from Zero

Last time Leet Code Day 44 "543. Diameter of Binary Tree" starting from zero

Right now, I'm prioritizing the Medium of the Top 100 Liked Questions. I solved all Easy, so if you are interested, please go to the table of contents.

Twitter I'm doing it.

problem

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

The difficulty level is Medium.

Given two binary trees, ʻoriginal and cloned, a reference to target of ʻoriginal is given.

The duplicated tree is a copy of the original tree and returns a reference to the same node in the duplicated tree. You are not allowed to modify the two trees or the target and the answer must be a reference to a node in the cloned tree.

Follow-up: If the tree allows repeat values, resolve the issue.

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.

I solved it as above. I thought it was a relatively good answer because I could write it simply, but I didn't get that much speed, so I looked up other answers.

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

This answer is written using que, but it should be easy to understand. The speed is perfect, and instead of forcing the problem into a type that you can solve, if you can learn how to answer like this and switch, it will be fun to solve the problem more!

Up to here for this time. Thank you for your hard work.