CS STUDY

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net DFS를 사용해 트리를 추적하는 문제이다. 먼저 말단 노드까지 도착한 뒤 올라오면서 왼쪽 오른쪽 자식 노드들의 길이와 합을 구한다. 트리의 지름은 무조건 왼쪽 최장경로 + 오른쪽 최장경로 이다. DFS로 리프 노드까지 내려간 뒤 해당 노드의 가중치를 리턴한다.그리고 자식 노드가 있는 부모 노드부터는 자식들의 경로들 중 가장 큰 두 길이를 선택한다.두 길이를 더한 것은 현재 노드..

트리 순회란 그래프 순회의 한 형태로 트리 자료구조에서 각 노드를 정확히 한 번 방문하는 과정을 말한다. 그래프 순회와 마찬가지로 트리 순회 또한 DFS 또는 BFS로 탐색하는데, 특히 이진트리에서 DFS는 노드의 방문 순서에 따라 다음과 같이 크게 3가지 방식으로 구분된다. 1. 전위 순회(preorder) - NLR 2. 중위 순회(inorder) - LNR 3. 후위 순회(post-order) - LRN L = 현재 노드의 왼쪽 서브트리 R = 현재 노드의 오른쪽 서브트리 N = 현재 노드 자신 class Node: def __init__(self,val,left=None,right=None): self.val=val self.left=left self.right=right root=Node('F'..

https://leetcode.com/problems/minimum-distance-between-bst-nodes/submissions/ Minimum Distance Between BST Nodes - 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. 재귀 구조로 중위 순회 BST의 왼쪽 자식은 항상 루트보다 작고, 오른쪽 자식은 항상 루트보다 크다. 그렇다면 루트 D와 가장 차이가 작을 수 있는 노드는 딱 2개 노드만 가능한데 바로 I와 G이다. 파란 글..

https://leetcode.com/problems/range-sum-of-bst/ Range Sum of BST - 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. 재귀 구조 DFS로 브루트 포스 탐색 DFS로 전체를 탐색한 다음, 노드의 값이 low와 high 사이일 때만 값을 부여하고, 아닐 경우에는 0을 취해 계속 더해 나가면 쉽게 구할 수 있다. # Definition for a binary tree node. # class TreeNode: # ..

정확히 중앙값을 갖도록 내림값을 리턴하는 // 연산자를 사용했다. # 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 sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]: if not nums: return None mid=len(nums)//2 node=TreeNode(nums[mid]) node.left=self.sortedArrayToBST(nums[:mid]) nod..

이진 탐색 트리(Binary Search Tree, BST)란 정렬된 트리를 말하는데, 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이뤄져 있는 반면, 노드의 오른쪽 서브트리에는 그 노드의 값과 같거나 큰 값들을 지닌 노드들로 이루어져 있는 트리를 뜻한다. 이 트리의 가장 훌룡한 점은 탐색 시 시간 복잡도가 O(log n)라는 점이다. BST는 랜덤하게 생성해도 대부분의 경우 균형이 잘 맞는 아름다운 형태로 트리를 표현할 수 있지만, 운이 나쁘면 트리의 모양이 균형을 제대로 이루지 못할 수 있다. 균형이 많이 깨지면 탐색 시에 O(log n)이 아니라 O(n)에 근접한 시간이 소요될 수 있다. 이런 트리는 균형을 맞춰 줄 필요가 있는데 그래서 고안해낸 것이 바로 '자가 균형 이진..

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 이하인 것을 말한다. 높이 균형은 매우 중요한 개념이다. 균형이 맞아야 효율적으로 트리를 구성할 수 있으며, 탐색 또한 더 효율적으로 처리할 수 있기 때문이다. 먼저 재귀 호출로 리프 노드까..

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 = ..