on
2021.11.03 [leetcode] Serialize and Deserialize Binary Tree...
2021.11.03 [leetcode] Serialize and Deserialize Binary Tree...
안녕하십니까 다제입니다.
오늘도 하루에 두 문제씩 열심히 코딩테스트 문제를 풀고 있습니다.
297. Serialize and Deserialize Binary Tree
[코드]
class Codec: def serialize(self, root): """Encodes a tree to a single string. :type root: TreeNode :rtype: str """ queue = collections.deque([root]) result = ["#"] while queue: node = queue.popleft() if node is not None: queue.append(node.left) queue.append(node.right) result.append(str(node.val)) else: result.append("#") return " ".join(result) def deserialize(self, data): """Decodes your encoded data to tree. :type data: str :rtype: TreeNode """ if data == "# #": return None nodes = data.split(" ") root = TreeNode(nodes[1]) queue = collections.deque([root]) index = 2 while queue: node = queue.popleft() if nodes[index] is not "#": node.left = TreeNode(int(nodes[index])) queue.append(node.left) index += 1 if nodes[index] is not "#": node.right = TreeNode(int(nodes[index])) queue.append(node.right) index += 1 return root
[실행 결과]
-. Runtime 112ms, faster than 89.11%
-. Memory Usage: 18.8 MB
[접근법]
먼저 비어있는 곳도 표시를 해주어야 하는데, None, Null을 이용하여 넣을 수 없다는 사실을 깨닫게 되었다. 이에, "#"을 넣어서 빈 곳을 표시해주기로 하였다. 큐를 이용하여 하나씩 순회하도록 하였고, 순회하면서 얻은 node.val을 result에 넣어주었다. 또한, if ~ else문을 사용하여 비어있는 곳의 값도 "#"로 넣어주었다. 중요한 것은 문제에서 배열로 리턴하라고 말을 하고 있기에 " ".join(result)를 통해 배열로 리턴을 해주었다. 역직렬화(트리화)가 더 재미있었는데, 배열을 리스트로 변경하고 어떻게 left와 right를 구분 할 수 있을까? 고민을 많이 하였다. 이진트리의 고유한 특성을 통해 이를 구별할 수 있었다. 오른쪽은 무조건 홀수 왼쪽은 짝수라는 성질이 있기 때문에 index에 1씩 더해주면서 오른쪽과 왼쪽을 구별할 수 있도록 하였다. 한 가지 중요한 것은 treeNode에 값을 넣을 때 int로 넣어야한다.
[느낀점]
링크드 리스트를 리스트로 변경한 것처럼 평소에 트리를 리스트로 변경하고 싶다는 생각을 많이 했는데 이번 문제를 통해서 어떻게 하는지 알게 되었다.
이진트리의 성질을 이용하여 왼쪽과 오른쪽을 구별하는 것은 정말 신기하고 brilliant했다!
110. Balanced Binary Tree
[코드]
class Solution: def isBalanced(self, root: Optional[TreeNode]) -> bool: def check(root): if not root: return 0 left = check(root.left) right = check(root.right) if left == -1 or right == -1 or abs(left-right) > 1 : return -1 return max(left, right) + 1 return check(root) != -1
[실행 결과]
-. Runtime 52ms, faster than 75.67%
-. Memory Usage: 15.6 MB
[접근법]
처음에는 높이를 구하는 문제에서 힌트를 얻어서 left, right를 빼려고 했었는데 이것은 최대 높이를 구하는 것이기 때문에 중간에 가지가 뻣어나긴 부분을 체크할 수 없어 일부 예제를 통과할 수 없었다. 이에, 모든 노드의 높이를 구하는 식으로 방향을 잡게 되었다. 앞쪽의 노드의 차이가 없다면 1씩 더해가고 1이상 차이가 난다면 -1로 값을 리턴해주는 식으로 코드를 구상해보았다.
[느낀점]
leetcode의 별 난이도는 특이한거 같다.. 이게 난이도 하라니..
from http://daje0601.tistory.com/300 by ccl(A) rewrite - 2021-11-03 12:00:43