CS STUDY

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)라고 구분해서 부른다. 이진 트리..