2021-01-03] Find a Corresponding Node of a Binary Tree in a Clone of That Tree

오늘의 문제:

leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/579/week-1-january-1st-january-7th/3590/

Account Login - LeetCode

 

처음 문제를 이해하는 데 진을 다 빼버려 정말 지쳐버렸다.. ( 영어가 어려운걸 떠나서, 문제를 이해 못했었음 )

 

역시 예시로 주어진 내용으로 내가 이해한 바를 설명한다.

 

<예시 5>

총 TreeNode를 input 값으로 3개를 넘겨준다. ( original, cloned, target )

 

original에서 원하는 값으로 target을 넘겨주고, cloned에서 target에 매칭되는 값을 출력해주는 것이다.

 

핵심은 target으로 주는 저것도 TreeNode이다. ( 처음에는 Node의 value 값인 int값으로 2를 넘겨주는줄 알았는데... 그것이 아님. 이거 때문에 삽질함..)

 

target은 original의 target(2)에서 시작하는 TreeNode를 말하는 것이고, 우리가 출력할 것은 cloned의 2에서 시작하는 TreeNode이다.

 

이제 문제는 이해했고, 어케 풀어야하나.. 결국 Tree 탐색 문제인 것이고, 이럴땐 BFS, DFS 각!!

 

문제풀이) BFS,DFS 풀이법으로 가즈아!!

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
def BFS(origin,cloned,target):
    temp = TreeNode()
    if origin == target: # origin의 TreeNode와 target의 TreeNode 형상비교
        return cloned # 같다면 그때의 cloned의 형상을 return
    if cloned.left and temp.val==0: # cloned의 left가 존재하고, temp값이 없다면 left 탐색
        temp=BFS(origin.left,cloned.left,target) # origin, cloned는 동일한 형상을 가져가주는 탐색
    if cloned.right and temp.val==0: # cloned의 right가 존재하고, temp값이 없다면 right 탐색
        temp=BFS(origin.right,cloned.right,target)
    return temp # 채워진 temp ( cloned의 target TreeNode 값 return )
class Solution(object):
    def getTargetCopy(self, original, cloned, target):
        """
        :type original: TreeNode
        :type cloned: TreeNode
        :type target: TreeNode
        :rtype: TreeNode
        """
        ans=BFS(original,cloned,target) # BFS로 값을 얻어버렷!!
        return ans