본문 바로가기
반응형

코딩테스트103

[LeetCode] 108. Convert Sorted Array to Binary Search Tree [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (정렬된 배열의 이진 탐색 트리 변환) 오름차순으로 정렬된 배열을 높이 균형(Height Balanced) 이진 탐색 트리로 변환하라. Input: nums = [-10,-3,0,5,9] Output: [0,-3,9,-10,null,5] or [0,-10,5,null,-3,null,9] 2. 풀이 재귀탐색을 이용한 풀이 3. 코드 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = righ.. 2021. 11. 24.
[LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (전위, 중위 순회 결과로 이진 트리 구축) 트리의 전위, 중위 순회로 결과를 입력값으로 받아 이진 트리를 구축하라. 2. 풀이 전위의 첫번 째 값은 부모 노드이며 중위 순회 결과를 left와 right로 나누는 역할을 한다. 전위 순회의 값을 순차적으로 빼면서 중위 순회를 left와 right로 나눈다. 3. 코드 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class .. 2021. 11. 24.
[LeetCode] 687. Longest Univalue Path [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (가장 긴 동일 값의 경로) 동일한 값을 지닌 가장 긴 경로를 찾아라. 2. 풀이 DFS를 이용한 풀이 3. 코드 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: result = 0 def longestUnivaluePath(self, root: TreeNode) -> int: def dfs(node: TreeNode): if node is Non.. 2021. 11. 24.
[LeetCode] 617. Merge Two Binary Trees [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (두 이진 트리 병합) 두 이진 트리를 병합하라. 중복되는 노드는 값을 합산한다. 2. 풀이 재귀탐색을 이용한 풀이 3. 코드 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode: if root1 and root2: node = Tr.. 2021. 11. 24.
[LeetCode] 297. Serialize and Deserialize Binary Tree [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (이진 트리 직렬화 & 역직렬화) 이진 트리를 배열로 직렬화하고, 반대로 역직렬화하는 기능을 구현하라. 다음과 같은 트리는 [1, 2, 3, null, null, 4, 5] 형태로 직렬화할 수 있다. 2. 풀이 BFS를 이용한 풀이 3. 코드 # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Codec: def serialize(self, root): """Encodes a tree to a single .. 2021. 11. 24.
[LeetCode] 226. Invert Binary Tree [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (이진 트리 반전) 중앙을 기준으로 트리를 반전하라. 2. 풀이 python의 특징을 이용한 풀이 BFS를 이용한 풀이 3. 코드 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def invertTree(self, root: TreeNode) -> TreeNode: # Python # if root: # root.left, root.right =.. 2021. 11. 24.
[LeetCode] 543. Diameter of Binary Tree [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (이진 트리의 직경) 이진 트리에서 두 노드 간 가장 긴 경로의 길이를 출력하라. 예를 들어, 위와 같은 트리는 4-2-1-3 or 5-2-1-3 으로 답은 3이다. 2. 풀이 DFS를 이용한 풀이 중첩 함수에서 숫자나 문자와 같은 불변 객체를 재할당하면 참조ID가 변경되므로 클래스 변수를 사용해야 한다! 3. 코드 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class .. 2021. 11. 24.
[LeetCode] 104. Maximum Depth of Binary Tree [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (이진 트리의 최대 깊이) 이진 트리의 최대 깊이를 구하라. 2. 풀이 BFS를 이용한 풀이 3. 코드 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def maxDepth(self, root: TreeNode) -> int: if root is None: return 0 q = collections.deque([root]) depth = 0 w.. 2021. 11. 24.
[LeetCode] 787. Cheapest Flights Within K Stops [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (K경유지 내 가장 저렴한 항공권) 시작점에서 도착점까지의 가장 저렴한 가격을 계산하되, K개의 경유지 이내에 도착하는 가격을 리턴하라. 경로가 존재하지 않을 경우 -1을 리턴한다. 2. 풀이 다익스트라 알고리즘을 이용한 풀이 collections.defaultdict(lambda : float('inf')) : 딕셔너리에 int의 최대값을 기본값으로 설정 3. 코드 import collections class Solution: def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int: .. 2021. 11. 24.
반응형

티스토리툴바