코린이의 소소한 공부노트

1. Input 1) int[] nums 2. Output 1) nums의 요소들로 높이 균형 이진 검색 트리를 만들어서 반환 - 답이 여러 가지일 경우 1개만 반환 3. Constraint 1) 1

1. Input 1) TreeNode root 2. Output 1) root가 좌우대칭 트리라면 true, 아니면 false를 반환 3. Constraint 1) 노드 수의 범위는 [1, 1000]이다. 2) -100 Output: false 5. Code /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left =..

1. 개념 정리 1) 이진 인덱스 구조를 활용하여 구간 합 문제를 효과적으로 해결해 줄 수 있는 자료구조 2) 펜윅 트리(Fenwick Tree)라고도 불린다. 3) 세그먼트 트리보다 구현하기 편하고 속도가 빠르다. - 세그먼트 트리는 필요한 리프 노드만 채우기 때문에 불완전 트리지만, 인덱스 트리는 리프 노드를 모두 채워서 만들기 때문에 인덱스를 활용할 수 있다. - 데이터의 개수가 N개일 때, 세그먼트 트리를 만들기 위해 필요한 공간을 통상 4*N만큼 준비했었다면 인덱스 트리를 만들 때는 N만큼만 준비하면 된다. 4) 인덱스는 1부터 사용하고, 인덱스를 활용하면 해당 인덱스의 값이 몇 개의 데이터의 합인지 알 수 있다. - 8비트로만 간단히 예시를 들어보면, 3과 -3을 비트 and 연산을 해보면 다..

1. 개념 정리 1) 여러 개의 데이터가 연속적으로 존재할 때 특정 구간의 데이터의 합을 담은 이진 트리 2) 실제 구현은 트리가 아닌 배열로 하게 된다. - 배열은 인덱스가 있어 접근성이 좋기 때문이다. 3) 세그먼트 트리를 이용한 구간 합 처리의 시간 복잡도는 O(lgn)이다. 2. 예시 1) 구간 합의 데이터가 될 배열을 준비한다. int[] arr = {1,2,3,4,5,6,7,8}; 2) 구간 합 트리가 될 배열도 준비한다. int[] tree = new int[32]; // arr.length * 4 // 데이터의 개수가 N개일 때 필요한 부분 합 트리의 공간은 // N 이상의 2의 거듭제곱수 중 가장 작은 것 * 2이다. // 여기서 N=8이므로 8 이상의 2의 거듭제곱수 중 가장 작은 것은..

1. Input 1) TreeNode root 2. Output 1) root에 있는 조건식을 계산한 결과를 반환 - leaf node: 0(false), 1(true) - non-leaf node: 2(OR), 3(AND) 3. Constraint 1) 노드 수의 범위는 [1, 1000]이다. 2) 0

1. Input 1) final TreeNode original 2) final TreeNode cloned - original을 복사한 트리 3) final TreeNode target - original의 노드 중 하나 2. Output 1) cloned에서 target과 같은 것을 찾아 반환 3. Constraint 1) 트리의 노드 수의 범위는 [1, 10^4]이다. 2) 노드의 값에는 중복이 없다. 3) 타겟 노드는 null이 아니다. 4. Example Input: tree = [7,4,3,null,null,6,19], target = 3 -> Output: 3 설명: 왼쪽 트리가 original, 오른쪽 트리가 cloned, 연두색이 target, 노란색이 반환해야 할 노드이다. 5. Cod..

1. Input 1) TreeNode root 2. Output 1) root의 모든 노드의 값이 같으면 true, 다르면 false를 반환 3. Constraint 1) 노드 수의 범위는 [1, 100]이다. 2) 0 Output: true Input: root = [2,2,2,5,2] -> Output: false 5. Code 1) 첫 코드(2023/06/06) /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, Tr..

1. Input 1) TreeNode root 2) int low 3) int high 2. Output 1) root에 있는 노드 값 중에서 [low, high] 범위 내의 값만 더한 결과를 반환 3. Constraint 1) 노드 수의 범위는 [1, 2*10^4]이다. 2) 1

1. Input 1) TreeNode root 2. Output 1) root를 inorder로 읽어온 후 모든 노드가 오른쪽 자식만 갖게 재배열한 결과를 반환 3. Constraint 1) 노드 수의 범위는 [1, 100]이다. 2) 0

1. Input 1) TreeNode root 2. Output 1) root에서 고른 임의의 두 값의 차가 가장 작은 것을 반환 - 차는 0 이상이어야 한다. 3. Constraint 1) 노드 수의 범위는 [2, 100]이다. 2) 0 Output: 1 5. Code 1) 첫 코드(2023/05/31) /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * th..