[LeetCode] 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree (Python)

• Reference
• dfs 방식으로 풀었다. (재귀)
• 파이참이 마지막줄에서 두번째인 self.answer 부분에 밑줄을 쳐서 hyun에게 도움을 요청했다.
  • 결론은 속도도 그렇고 if문이 안 돌면 self.answer가 생성이 안 되니 앞으로는 꼭 생성해주자!
• 생성자 X
  • Runtime 632 ms
  • Beats 43.13%
• 생성자 O
  • Runtime 624 ms
  • Beats 52.38%
• 시간복잡도: $O(N)$

Solution

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


class Solution:
    # 추가된 생성자
    def __init__(self):
        self.answer = None

    def getTargetCopy(self, original: TreeNode, cloned: TreeNode, target: TreeNode) -> TreeNode:
        self.inorder(original, cloned, target)
        return self.answer

    def inorder(self, original: TreeNode, cloned: TreeNode, target: TreeNode):
        if original:
            self.inorder(original.left, cloned.left, target)
            if original is target:
                self.answer = cloned
            self.inorder(original.right, cloned.right, target)