본문 바로가기
반응형

Tree10

[Leetcode] 94. Binary Tree Inorder Traversal 문제 : https://leetcode.com/problems/binary-tree-inorder-traversal/ 이진 트리의 루트가 입력값으로 주어지면 중위 순회한 결과를 반환해라. 재귀함수를 하나만들고 왼쪽 자식 노드로 탐색. 현재 노드의 값을 정답 배열에 저장. 오른쪽 자식 노드로 탐색. 만일 현재 탐색하는 노드가 null 이면 재귀함수를 종료한다. 시간복잡도는 O(N). N = 이진트리 노드 수 소스코드 : 2021. 11. 5.
[Leetcode] 222. Count Complete Tree Nodes 문제 : https://leetcode.com/problems/count-complete-tree-nodes/ 완전 이진 트리(complete binary tree)의 루트 노드가 입력으로 주어지면 트리의 노드 수를 반환해라. 시간복잡도를 O(N) 보다 작게 만들어라. 포화 이진 트리의 노드 수는 2^(트리 높이) - 1 임을 사용하자. 최좌측 단노드까지의 높이와 최우측 단노드까지의 높이가 같은 경우 포화 이진 트리가 된다. 높이가 다른 경우, 왼쪽 하위 노드들 수와 오른쪽 하위 노드들 수를 구해서 더하고 루트 노드 수인 1을 더한 값이 노드 수가 된다. 왼쪽 하위 노드들 수와 오른쪽 하위 노드들 수는 재귀함수를 이용해 구한다. 완전이진트리인지 구하기 위해 log2N이 소요되고, 최악의 경우 높이를 탐색.. 2021. 10. 29.
[leetcode] 236. Lowest Common Ancestor of a Binary Tree 문제 : https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/ 트리가 주어질 때, 노드 p, q의 최하위 공통조상(LCA; Lowest Common Ancestor)를 찾아라. 재귀함수로 풀었다. 이 함수는 탐색하는 노드를 루트로 하는 서브트리에서 p, q를 찾은경우 해당 노드를 반환하거나, 만약 두노드의 최하위 공통조상인 경우 해당 노드를 반환한다. p, q 가 서브트리에 없는 경우는 NULL을 반환한다. 현재 탐색 중인 노드가 p 또는 q 인 경우 현재 노드를 반환한다. 왼쪽 자식, 오른쪽 자식들을 탐색노드로 함수를 호출한다. 왼쪽, 오른쪽 자식들에서 p, q를 찾았다면(NULL이 아니라면) 현재 탐색중인 노드가 LCA가 되므로.. 2021. 7. 22.
[Programmers] 다단계 칫솔 판매 문제 : https://programmers.co.kr/learn/courses/30/lessons/77486 추천인을 저장하는 parentMap(key = 판매원, value = 추천인)과 총 이익을 저장하는 priceMap(key = 판매원, value = 이익)을 만든다. enroll, referral 을 탐색하며 parentMap을 세팅한다. seller, amount 배열을 탐색하며 priceMap 을 세팅해보자. 얻은 이익은 칫솔가격이 100이므로 amount[i] * 100이다. 이익의 10프로를 제외한 가격을 자신한테 더하고 10프로는 추천인한테 배분한다. 만약 parentMap[탐색중인 판매원] value가 "-"가 아닌 경우 이익의 분배를 다시 해야하므로 parentMap[탐색중인 판매.. 2021. 6. 1.
트리의 지름 트리의 지름은 트리의 노드들 중 가장 먼 거리를 가지는 두 노드 사이의 거리를 의미합니다. 알고리즘 1. 임의의 노드 x를 선택한다. 2. dfs로 x와 가장 먼 노드(A)를 구한다. 만약 가장 먼 노드가 2개 이상이라면 이들 중 어떠한 것을 선택해도 상관없다. 3. dfs를 한 번 더 돌려서, 노드 A로부터 가장 먼 노드(B)를 구한다. 4. 노드 A와 노드 B의 거리가 트리의 지름이 된다. 노드 사이의 거리인데 최단거리 알고리즘을 돌려야하지 않나?! 싶기도 하지만 "트리"의 지름을 구하고 있음을 유의해봅시다. 트리의 성질 중 "트리의 두 노드 사이의 경로는 하나만 존재한다."가 있습니다. 따라서 dfs 탐색 중에 구해지는 노드 사이의 거리가 최단거리가 됩니다. 참고코드 : github.com/fpdj.. 2021. 2. 21.
[leetcode][116] Populating Next Right Pointers in Each Node 문제 : leetcode.com/problems/populating-next-right-pointers-in-each-node/ 같은 depth를 가진 노드들을 왼쪽에서부터 오른쪽 형제들을 각 노드들의 next 포인터로 연결한다. 노드들을 왼 -> 오 순으로 연결하기 때문에 노드들을 탐색하면서 왼쪽 자식, 오른쪽 자식 순으로 탐색해나간다. 같은 depth를 가진 노드들을 연결하기 때문에 depth를 key 값으로 하고 해당 depth들 중 가장 마지막에 탐색된 노드 포인터를 value 값으로 하는 map을 만든다. 탐색하면서 탐색 중인 노드의 depth로 가장 마지막 노드 정보를 가져와서 가져온 노드의 next 포인터에 현재 탐색 중인 노드 포인터를 넣는다. 그리고 value 를 현재 탐색중인 노드로 갱.. 2020. 11. 15.
반응형