2021.10.06 [leetcode] Invert Binary Tree, Merge Two Binary Trees

2021.10.06 [leetcode] Invert Binary Tree, Merge Two Binary Trees

안녕하십니까 다제입니다.

오늘도 하루에 두 문제씩 열심히 코딩테스트 문제를 풀고 있습니다.

226 . Invert Binary Tree( 이진 트리 반전)

[코드]

class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if root : root.left, root.right = self.invertTree(root.right), self.invertTree(root.left) return root return None

[실행 결과]

-. Runtime 32 ms

-. Memory Usage: 14.2 MB

[접근법]

다중할당을 이용하여 문제를 풀면 될 거 같다는 생각이 빡 들었고, 재귀를 사용하면 되겠다라는 생각이 팍 들었다. 클래스 내에서 재귀를 할당하는 부분을 찾느라 고생을 조금 하였지만, 금방 찾고 이해하게 되었다.

[느낀점]

이제는 보면 아 어떻게 풀면 되겠구나 라는 직감 정도는 오는정도라고 할 수 있다.

코로나 2차 백신으로 잠을 푹 잤더니 머리가 맑아져서 그런걸까?ㅎ

617 . Merge Two Binary Trees( 이진 트리 병합)

[코드]

class Solution: def mergeTrees(self, t1: Optional[TreeNode], t2: Optional[TreeNode]) -> Optional[TreeNode]: if t1 and t2: node = TreeNode(t1.val + t2.val) node.left = self.mergeTrees(t1.left, t2.left) node.right = self.mergeTrees(t1.right, t2.right) return node else: return t1 or t2

[실행 결과]

-. Runtime 84ms

-. Memory Usage: 15.6 MB

[접근법]

새로운 트리를 만들어주어야 합니다. Null과 int가 연산이 되지 않기 때문에 값이 모두 있는 것과 값이 한쪽만 있는 것을 구분하여 코드를 작성해주어야 합니다. 이에, 값이 양쪽 트리에 모두 있는 경우는 t1.val + t2.val을 하여 더해주고 재귀로 진행합니다. 그리고 null 이 있는 곳에는 있는 값이 오도록 코드를 작성합니다.

[느낀점]

노드를 이렇게 더해서 만들 수 있다는 생각은 처음 해보았다..

이와 더불어 첫날꺼부터 다시 복습을 해보고 있습니다. 잊어버리지 않는 것이 더 중요하다고 생각해서요 오늘은 "유효한 팰린드롬", "문자열 뒤집기"를 복습하였습니다. 여러분도 힘내세요! 피가 되고 살이 됩니다.

from http://daje0601.tistory.com/298 by ccl(A) rewrite - 2021-11-02 18:26:23