본문 바로가기
728x90
반응형

BST8

530. Minimum Absolute Difference in BST 이진 탐색 트리(Binary Search Tree, BST)의 루트 노드가 주어졌을 때, 트리 내의 어떤 두 다른 노드 값 사이의 최소 절대 차이를 반환하는 문제입니다. 예제: 예제 1: 입력으로 root = [4,2,6,1,3]이 주어지면, 출력은 1입니다. 예제 2: 입력으로 root = [1,0,48,null,null,12,49]이 주어지면, 출력은 1입니다. 제약 조건: 트리의 노드 수는 범위 [2, 10^4] 내에 있습니다. 0 오른쪽 자식 노드 순서로 노드를 방문합니다. 이 방법을 사용하면 이진 탐색 트리의 노드들이 오름차순으로 방문되므로, 각 노드와 이전 노드의 차이를 계산하여 최소 절대 차이를 찾습니다. 이진 탐색 트리 root = [4,2,6,1,3]에 대해 중위 순회를 실행하면 다음과 .. 2024. 4. 21.
637. Average of Levels in Binary Tree 이진 트리의 각 레벨에 있는 노드들의 평균 값을 계산하는 문제입니다. 이진 트리의 루트가 주어지면, 각 레벨의 노드들의 평균 값을 배열 형태로 반환해야 합니다.이진 트리의 각 레벨에 있는 노드들의 평균 값을 계산하는 문제입니다. 이진 트리의 루트가 주어지면, 각 레벨의 노드들의 평균 값을 배열 형태로 반환해야 합니다. 실제 답과 10^-5 이내의 오차는 허용됩니다. /** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode .. 2024. 4. 18.
162. Find Peak Element 어진 정수 배열에서 peak element를 찾는 문제입니다. Peak element는 해당 위치에서 좌우의 원소보다 큰 값을 갖는 원소를 의미합니다. 예를 들어, 배열 [1, 2, 3, 1]에서 3은 peak element입니다. 배열 [1, 2, 1, 3, 5, 6, 4]에서 6도 peak element입니다. 이 문제를 풀기 위한 일반적인 방법은 이진 검색(Binary Search)을 사용하는 것입니다. 이진 검색을 사용하면 O(log N)의 시간 복잡도로 peak element를 찾을 수 있습니다. public int FindPeakElement(int[] nums) { if (nums.Length == 0) { return -1; // 배열이 비어있는 경우 } // 배열의 길이가 1인 경우 if.. 2023. 11. 16.
110. Balanced Binary Tree 주어진 이진 트리가 균형 잡힌 트리인지 확인하세요. 균형 잡힌 트리는 모든 서브트리의 높이 차이가 1 이하인 트리를 의미합니다. 즉, 모든 서브트리가 높이 균형을 유지하고 있는 경우 균형 잡힌 트리입니다. 예를 들어, 다음은 균형 잡힌 트리입니다: 3 / \ 9 20 / \ 15 7 각 서브트리의 높이 차이가 1 이하입니다. 반면에, 다음 트리는 균형 잡힌 트리가 아닙니다: 1 / \ 2 2 / \ 3 3 / \ 4 4 여기서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 2이므로 균형 잡힌 트리가 아닙니다. 균형 잡힌 트리 여부를 판단하기 위해, 주어진 트리의 각 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이를 비교하여 높이 차이가 1 이하인지 확인해야 합니다. 이 작업을 트리의 모든 노드에 대해 재.. 2023. 11. 4.
94. Binary Tree Inorder Traversal 이진 트리의 노드를 중위 순회(inorder traversal)하여 노드 값들을 리스트에 저장하는 문제입니다. 중위 순회는 트리를 다음과 같은 방식으로 순회합니다: 먼저, 왼쪽 하위 트리를 순회합니다. 현재 노드를 방문하고 처리합니다. 마지막으로, 오른쪽 하위 트리를 순회합니다. 즉, 이 문제에서는 이진 트리를 중위 순회하여 노드 값을 리스트에 저장해야 합니다. 문제 설명: 주어진 이진 트리의 루트 노드 root가 주어집니다. 이 트리를 중위 순회하여 나오는 노드 값들을 리스트에 저장하고, 그 리스트를 반환하세요. 예시: 만약 주어진 이진 트리가 다음과 같다고 가정하면: 1 \ 2 / 3 중위 순회를 수행하면 노드 값 [1, 3, 2] 순서대로 리스트에 저장하고 반환해야 합니다. 노트: 중위 순회를 재귀.. 2023. 10. 30.
108. Convert Sorted Array to Binary Search Tree 주어진 정렬된 정수 배열을 사용하여 균형 잡힌 이진 검색 트리(Binary Search Tree)를 만드는 문제입니다. 아래는 문제의 자세한 설명입니다: 문제 설명: 주어진 정렬된 정수 배열 nums를 사용하여 높이 균형을 갖는 이진 검색 트리를 생성하세요. 이진 검색 트리는 다음과 같은 조건을 만족해야 합니다: 노드의 왼쪽 서브 트리에는 해당 노드보다 작은 값의 노드들만 포함되어야 합니다. 노드의 오른쪽 서브 트리에는 해당 노드보다 큰 값의 노드들만 포함되어야 합니다. 각 서브 트리도 이진 검색 트리여야 합니다. 예시: 주어진 nums 배열이 [1, 2, 3]라면, 다음과 같은 이진 검색 트리를 생성해야 합니다: 2 / \ 1 3 노트: nums 배열의 길이는 1 이상 10^4 이하입니다. nums 배.. 2023. 10. 25.
Binary Search Tree : Insertion BST에 노드를 삽입하는 과정은 다음과 같습니다: 루트 노드부터 시작합니다. 현재 노드의 값과 삽입하려는 데이터 값을 비교합니다. 삽입하려는 데이터 값이 현재 노드의 값보다 작으면 왼쪽 서브트리로 이동하고, 값이 크면 오른쪽 서브트리로 이동합니다. 만약 해당 서브트리가 비어있으면 새로운 노드를 생성하고 그 위치에 삽입합니다. 만약 해당 서브트리가 비어있지 않다면 서브트리의 루트로 이동하여 2단계부터 반복합니다. 모든 작업이 완료되면 변경된 BST의 루트 노드를 반환합니다. BST에 노드를 삽입하는 이 과정을 재귀적으로 구현하거나 반복문을 사용하여 구현할 수 있습니다. 주어진 문제에서는 이 과정을 잘 구현하여 새로운 노드를 BST에 삽입하고 변경된 BST의 루트 노드를 반환하는 함수를 작성해야 합니다. N.. 2023. 10. 6.
728x90
반응형

티스토리툴바