[99클럽 코테스터디 2기][Python/비기너] 12번째 문제: Find a Corresponding Node of a Binary Tree in a Clone of That Tree

오늘의 주제는 깊이/너비 우선 탐색(DFS/BFS)

[Find a Corresponding Node of a Binary Tree in a Clone of That Tree]

문제

입력과 출력

코드

# 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:
        
        def dfs(node,ref,target):
            if not node:
                return 
            if node==target:
                return ref
            else:
                return dfs(node.left, ref.left, target) or dfs(node.right, ref.right, target)
        
        return dfs(original,cloned, target)

알고리즘
#트리를 탐색하여 target과 값이 같을 때 return해준다.
먼저 노드가 없을때 반환해주는 조건문을 달아준다.
그리고 노드와 타겟이 같을때 cloned에서 반환해준다.
같지 않을 때 왼쪽 노드 혹은 오른쪽 노드 반환해준다.

회고
어제 풀었던 트리문제를 토대로 코드를 구성해보았다.

class Solution:
    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        visited=[]
        def dfs(node):
            if not node:
                return
            if node.val!=target:
                visited.append(node)
                if node in visited:
                    
                dfs(node.left)
                dfs(node.right)
            elif node.val==target:
                return node.val
        return dfs(original)

처음 코드는 이런식으로 구성했었다. visited 부분은 dfs 코드에서 봤던 기억이 떠올라서 추가해보려고 시도했지만, 실패한 부분..

이 사진에서는 마지막에 함수를 호출해주는 부분이 누락되었는데 함수를 추가했을 때의 결과는
node.val 에서 오류가 났는데, int에는 val이 없다는 내용이었다..
어제 같은 형식으로 했을 때는 됐는데...? 왜 treenode형식인데 .. 이렇게 되지...?
했는데 자세히 보니 target도 Treenode 형식이었다.. 당연히 불가능했던 비교였던 것이다 ㅎ
그리고 target도 treenode 형식이니 굳이 val값을 비교하지 않고 객체자체를 비교하면 되겠다고 생각했다.
추가로, visited는 필요가 없을거 같아 제외하고 코드를 구성했고
비교는 original에서 하되, 반환은 cloned에서 해야하므로 이 부분도 함께 수정해주었다.

완성된 코드!

코딩스터디를 시작하기 전에 첫 코테 공부를 시작했을 때, dfs 알고리즘을 보고 ..멍했었는데
어제 문제를 제대로 이해하고, 이를 사용해서 오늘 문제를 시도해보고 하는 과정에서 조금 가까워진것 같아 뿌듯하다..!!

• 너비 우선 탐색 알고리즘도 함께 공부해보자
• 깊이 우선 탐색 알고리즘도 다양하니 좀 더 참고해보자