# 트리
[TIL-20210618] 그래프(Graph) & 트리(Tree)
그래프 컴퓨터 공학에서 이야기 하는 자료구조 그래프는 마치 거미줄처럼 여러개의 점들이 선으로 이어져 있는 복잡한 네트워크 망과 같은 모습을 가지고 있다.[그림] 그래프 예시 그래프 관련 용어 정리 정점(vertex): 하나의 점 / 위치라는 개념 간선(edge): 위치
[Baekjoon] 11725. 트리의 부모 찾기
문제 링크트리그래프 탐색실버 2노드가 N개이고 1이 루트인 트리의 간선 N-1개가 입력될 때, 2~N번 노드의 부모를 각각 출력하기처음에는 edge를 따로 저장하지 않고 입력 받을 때마다 이전까지 연결된 트리에 연결하는 방식을 사용했다.부모가 정해진 노드들의 부모 정보
2250. 트리의 높이와 너비
2250\. 트리의 높이와 너비 예시에는 root node가 1번부터 시작하고 맨 위에 존재하지만, 문제 case에는 root node부터 시작하지 않을 수도, node의 순서대로 들어오지 않을 수 있다. level을 2\*\*level - 1 방식으로 해보려고 했는데
[알고리즘] 백준 - 트리
백준 - 트리전위 순회는 root -> left -> right, 중위 순회는 left -> root -> right, 후위 순회는 left -> rigt -> root 순으로 이루어진다.여기서 우리는 전위 순회로 루트를 구하고, 구한 루트를 기반으로 중위 순회를 통해
백준 20924 트리의 기둥과 가지
문제링크 https://www.acmicpc.net/problem/20924 문제 풀이 두 번의 dfs를 이용해 풀이했다. 첫 번째 dfs에서 기둥의 길이와 기가 노드를 찾아주었다. 두 번째 dfs의 시작점을 기가 노드로 지정하여 가장 긴 가지를 찾아주었다. 방문한 노드는 visit 배열을 통해 표시하여 두 번째 dfs 실행 시 기둥 노드에 방문하지 않...
JS 자료구조와 알고리즘(7)
각 노드가 하나 혹은 2개의 자식 노드만을 가지고 있는 상태의 트리구조이다perfect binary trees모든 노드가 2개의 노드를 가지고 있으며, 값이 채워져있는 형태의 바이너리 트리이다!아주 효율적이다!왜why??? 한 레이어 아래로 내려가면 노드의 수는 2배가
[트리] 리트코드 226: invert binary tree
Given the root of a binary tree, invert the tree, and return its root.
.jpg?w=120)
백준 2263번 - 트리의 순회
트리의 중위 순회 후위 순회를 입력 받아서 전위 순회의 결과를 출력하는 문제분할 정복으로 풀이를 한다.위 트리에서 후위 순회로 각 서브트리에 대해서 마지막 원소는 트리의 부모 노드가 된다.ex) 후위 순회 - 8 9 4 5 2 6 7 3 (1) <- 부모 노드이자
[트리] 리트코드 687: longest-univalue-path
Given the root of a binary tree, return the length of the longest path, where each node in the path has the same value.
백준 1167 트리의 지름
문제링크 https://www.acmicpc.net/problem/1167 문제 풀이 처음에는 그냥 모든 단말노드에서 DFS를 돌려주어 트리의 지름을 찾으려 했다. 정점의 개수가 2<=V<=100000이니 당연히 시간 초과가 났다. DP로 접근하려고도 생각해 보았는데 저 범위에서는 어차피 메모리 초과가 날것이므로 따로 시도는 안했다. 고민하던중 .. 임의...
