Tree12 [Leetcode] 623. Add One Row to Tree 문제 : https://leetcode.com/problems/add-one-row-to-tree/ 루트부터 자식으로 탐색해가면서 현재 depth가 새로운 노드가 추가되어야 하는 위치의 부모 노드라면 (1) (depth-1 이라면) 새로운 노드를 만들고 왼쪽 자식 노드에 들어갈 새로운 노드의 왼쪽 자식엔 원래의 왼쪽 자식 노드를 연결(2)한다. 오른쪽 자식 노드에 들어갈 새 노드의 오른쪽 자식엔 원래 오른쪽 자식 노드를 연결(3)한다. 새로 만든 노드들을 탐색 중인 노드의 자식 노드들로 연결(4)한다. 시간 복잡도는 O(N). N = 노트 수 소스코드 https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/623.%20Add%20One%20Ro.. 2022. 10. 5. [Leetcode] 662. Maximum Width of Binary Tree 문제 : https://leetcode.com/problems/maximum-width-of-binary-tree/ 이진 트리의 루트가 주어지면 트리의 최대 너비를 구하라. 최대 너비는 모든 레벨 중 최대 너비이며, 한 레벨의 너비는 가장 왼쪽 노드와 가장 오른쪽 노드의 길이이다. 만약 노드들 사이에 null 노드가 존재한다면 null 노드도 길이에 포함시킨다. 이진트리의 인덱스를 구해보면 위와 같다. 특정 노드의 왼쪽 자식 노드의 인덱스는 2 x 인덱스. 오른쪽 자식 노드의 인덱스는 2 x 인덱스 + 1 이다. 이를 이용하여 루트 노드부터 자식 노드들을 탐색해가며 각 레벨에서 가장 왼쪽에 존재하는 노드와 가장 오른쪽에 존재하는 노드의 인덱스 차이가 너비가 된다. 구한 너비들 중 최대값이 정답이 된다. .. 2022. 2. 27. [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 2 다음
