CS STUDY

https://leetcode.com/problems/minimum-height-trees/submissions/ Minimum Height Trees - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 최소 높이를 구성하려면 가장 가운데에 있는 값이 루트여야 한다. 이 말은 리프 노드를 하나씩 제거해 나가면서 남아 있는 값을 찾으면 이 값이 가장 가운데에 있는 값이 될것이고, 이 값을 루트로 했을 때 최소 높이를 구성할 수 있다는 뜻이기도 하다. 이 문제에서 그..

https://leetcode.com/problems/balanced-binary-tree/ Balanced Binary Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 이진 트리가 높이 균형인지 판단하라. 높이 균형은 모든 노드의 서브 트리 간의 높이 차이가 1 이하인 것을 말한다. 높이 균형은 매우 중요한 개념이다. 균형이 맞아야 효율적으로 트리를 구성할 수 있으며, 탐색 또한 더 효율적으로 처리할 수 있기 때문이다. 먼저 재귀 호출로 리프 노드까..

list(map(int,str(i))) 이 코드를 통해 만약 str(i)='321'이라면 [3,2,1]이 출력된다.

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/ Serialize and Deserialize Binary Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com BFS를 통해서 직렬화를 구현해보자. # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x #..

https://leetcode.com/problems/merge-two-binary-trees/submissions/ Merge Two Binary Trees - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 이 문제는 재귀탐색으로 해결할 수 있다. # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = ..

https://leetcode.com/problems/invert-binary-tree/ Invert Binary Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. 파이썬 다운 방식 이 문제는 재귀를 통해 파이썬다운 방식으로 정말 쉽게 풀 수 있다. 그러나 막상 설명은 쉽지 않다. class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if root:..

이진 트리에서 두 노드 간 가장 긴 경로의 길이를 출력하라. https://leetcode.com/problems/diameter-of-binary-tree/ Diameter of Binary Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 가장 긴 경로를 찾는 방법은 먼저 가장 말단, 즉 리프 노드까지 탐색한 다음 부모로 거슬러 올라가면서 각각의 거리를 계산해 상태값을 업데이트 하면서 다음과 같이 누적해 나가면 된다. 최종 루트에서 상태값은 2, 거..

https://leetcode.com/problems/maximum-depth-of-binary-tree/ Maximum Depth of Binary Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 깊이는 여러 가지 방법이 있지만 여기서는 BFS로 풀이해 보겠다. DFS는 스택, BFS는 큐를 사용하여 구현한다. 큐 변수에는 현재 깊이 depth에 해당하는 모든 노드가 들어 있고, queue.popleft()로 하나씩 끄집어 내면서 cur_root.h..

트리를 본격적으로 살펴보기에, 앞서 트리 각 부분에 대한 명칭을 살펴보자. 그래프 vs 트리 그래프와 트리의 차이점은 트리는 순환 구조를 갖지 않는 그래프임 이다. 트리는 크게 그래프의 범주에 포함되지만 그래프와 달리 트리는 어떠한 경우에도 한번 연결된 노드가 다시 연결되는 법이 없다. 이외에도 트리는 부모 노드에서 자식 노드를 가리키는 단방향뿐이다. 이진 트리 트리중에서 가장 널리 사용되는 트리 자료구조는 이진 트리와 이진 탐색 트리(Binary Search Tree,BST)이다. 각 노드가 m개 이하의 자식을 갖고 있으면, m-ary 트리(다항 트리, 다진 트리)라고 한다. m=2일 경우, 즉 모든 노드의 차수가 2 이하일 때는 특별히 이진 트리(Binary Tree)라고 구분해서 부른다. 이진 트리..

https://leetcode.com/problems/cheapest-flights-within-k-stops/ Cheapest Flights Within K Stops - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 시작점에서 도착점까지의 가장 저렴한 가격을 계산하되, K개의 경유지 이내에 도착하는 가격을 리턴하라. 경로가 존재하지 않을 경우 -1을 리턴한다. 여기서는 앞에 문제와 비교했을때 한 가지 제약사항이 추가되었는데 K개의 경유지 이내에 도착해야 한다..