본문 바로가기

Coding Test/LeetCode57

[LeetCode] 1038. Binary Search Tree to Greater Sum Tree [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (이진 탐색 트리(BST)를 터 큰 수 합계 트리로) BST의 각 노드를 현재값보다 더 큰 값을 가진 모든 노드의 합으로 만들어라. Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8] ex : 4 -> 4 + 5 + 6 + 7 + 8 = 30 2. 풀이 재귀탐색을 이용한 풀이 중위 순회로 노드 탐색 right -> now -> left 3. 코드 # Definition for a binary tree node. # class TreeNod.. 2021. 11. 24.
[LeetCode] 938. Range Sum of BST [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (이진 탐색 트리(BST) 합의 범위) BST가 주어졌을 때 L 이상 R 이하의 값을 지닌 노드의 합을 구하라. Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8] ex : 4 -> 4 + 5 + 6 + 7 + 8 = 30 2. 풀이 재귀탐색과 DFS를 이용한 풀이 반복문과 DFS를 이용한 풀이 3. 코드 재귀탐색과 DFS를 이용한 풀이 # Definition for a binary tree node. # class TreeNode: # .. 2021. 11. 24.
[LeetCode] 783. Minimum Distance Between BST Nodes [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (이진 탐색 트리(BST) 노드 간 최소 거리) 두 노드 간 값의 차이가 가장 작은 노드의 값의 차이를 출력하라. 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: pre, ret = -100000, 100000 def minDi.. 2021. 11. 24.
[LeetCode] 310. Minimum Height Trees [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (최소 높이 트리) 노드 개수와 무방향 그래프를 입력받아 트리가 최소 높이가 되는 루트의 목록을 리턴하라. Input: n = 4, edges = [[1,0],[1,2],[1,3]] Output: [1] Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]] Output: [3,4] 2. 풀이 노드가 2개 이하가 될때까지 리프 노드를 순차적으로 제거한다 3. 코드 class Solution: def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]: if n == 1: return [0] graph =.. 2021. 11. 24.
[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.

티스토리툴바