1379-kir3i.md

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

Solution

• 시간복잡도: O(N) (N은 트리의 노드의 수)

• 알고리즘

  BFS, DFS, 트리 순회

• 풀이설명

  cloned를 순회하며 같은 val을 갖는 노드에 도착할 시 해당 노드를 반환합니다. 아래 코드에서는 트리 순회 방법으로 BFS를 사용했습니다.

• 소스코드

# 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, cloned, target):
        q = []
        q.append(cloned)

        while q:
            curr = q.pop()
            if curr.val == target.val:
                return curr

            if curr.left:
                q.append(curr.left)
            if curr.right:
                q.append(curr.right)