[99클럽 코테 스터디] 1일차 TIL - 깊이/너비 우선 탐색(DFS/BFS), Find a Corresponding Node of a Binary Tree in a Clone of That Tree

[1일차] 깊이/너비 우선 탐색(DFS/BFS)

 

문제: https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree/

* 대충 번역: TreeNode 클래스 변수인 original과 그의 복사본 cloned가 있다. original의 target 노드와 같은 노드를 cloned에서 찾아 리턴하라.

Solution

문제 해결의 요지는 주어진 클래스를 이해하는 것이다.

정의된 TreeNode 클래스에 접근할 수 있는 인스턴스 변수가 val, left, right 이다.

우리는 루트 노드에는 바로 접근할 수 있고, 원하는 노드를 찾기 위해서는 루트에서 시작해서 반복 호출해 주어야 한다.

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

class Solution(object):
    def getTargetCopy(self, original, cloned, target):
        """
        :type original: TreeNode
        :type cloned: TreeNode
        :type target: TreeNode
        :rtype: TreeNode
        """
        if original is None:
            return None
        
        if original == target:
            return cloned
        
        left = self.getTargetCopy(original.left, cloned.left, target)
        if left is not None:
            return left
        
        return self.getTargetCopy(original.right, cloned.right, target)

출처: ChatGPT ..

나다어

• 클래스 구조 이해하기. 문제만 읽고 주석 코드를 무시해서 리스트인 줄 알고 find, index 함수 쓴 .. 
• 재귀를 구현하기 위해서는 여러 스탭을 한 번에 생각해서는 안된다. 무조건 하나의, n번째 케이스에 대한 구조를 짜야한다. 다시 말해 모든 경우의 수를 한 번에 커버하는 코드를 생각하면, 오히려 잘못된 코드를 짜게 된다. 단순하게 생각하자!