[LeetCode 리트코드] Find a Corresponding Node of a Binary Tree in a Clone of That Tree

문제

바이너리 트리 original이 주어진다. 그리고 그것의 레퍼런스 버전인 cloned가 주어진다. target노드가 head가 되는 cloned된 트리를 리턴하라.

언뜻 보면 되게 간단하다. 그냥 bfs로 돌면서 target과 value가 같은 노드가 있으면 리턴하면 된다.

예

추가사항

• 노드의 개수는 1개 이상 10^4개 이하
• target 노드는 무조건 original 중에 있음

 

 

나의 솔루션

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
def bfs(node: TreeNode, val):
    if node.val == val:
        return node
    if node.left:
        result1 = bfs(node.left, val)
        if result1:
            return result1
    if node.right:
        result2 = bfs(node.right, val)
        if result2:
            return result2
       
    
class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        return bfs(cloned, target.val)
    

 

깨달은 점

You returned the target node. You must return a reference to it in the cloned tree. 라는 에러가 처음에 떴었다.

도대체 뭐가 문제지... 하고 한참을 헤맨 결과... 

마지막줄에 return bfs(original, target.val) 이라고 쓴 것.... cloned를 넘겼어야했는데ㅠㅠ 

오늘의 삽질 끝...

 

결과

Submission Detail

56 / 56 test cases passed.	Status: Accepted
Runtime: 600 ms Memory Usage: 24.2 MB	Submitted: 0 minutes ago