❒ Description날짜2024.09.26 (목)레벨Medium제목Construct BT from Preorder and Inorder Traversal링크https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/자료구조그래프 - BST시간 복잡도O(n)      ❒ 문제 및 로직 분석int[] preorder = {1, 2, 4, 5, 3, 6, 7, 9, 8}; // 전위 순회int[] inorder = {4, 2, 5, 1, 7, 9, 6, 8, 3}; // 중위 순회 전위 순회의 첫 번째 값은 항상 root 노드다. 즉, 전위 순회의 첫 번째 결과는 정확히 중위 순회 결과..

❒ Description날짜2024.09.25 (수)레벨Easy제목Minimum Distance Between BST Nodes링크https://leetcode.com/problems/minimum-distance-between-bst-nodes/description/자료구조그래프 - BST시간 복잡도O(n) [LeetCode#1038] Binary Search Tree to Greater Sum Tree 문제와 거의 유사한 문제이다.     ❒ Solutionprivate int prev = Integer.MIN_VALUE + 10000;private int minDiff = Integer.MAX_VALUE;public int minDiffInBST(TreeNode root) { if (root ..

❒ Description날짜2024.09.25 (수)레벨Easy제목Range Sum of BST링크 https://leetcode.com/problems/range-sum-of-bst/description/자료구조BST     ❒ 문제 분석트리에서 부모노드 보다 작은 노드는 왼쪽으로, 큰 노드는 오른쪽에 위치한다. 이번 문제에서는 가장 작은 값 low와가장 큰 값 high를 제시해준다. 따라서 재귀 구조로 트리를 순회할 때 현재 노드의 값이 low 보다 작다면 오른쪽만탐색하고, 현재 노드의 값이 high 보다 크다면 왼쪽만 탐색한다. root root > high : 왼쪽만 탐색    ❒ Solution1. 트리의 특징을 통한 문제해결public int rangeSumBST(TreeNode root, i..

❒ Description날짜2024.09.25 (수)레벨Medium제목Binary Search Tree to Greater Sum Tree링크 https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/description/자료구조BST     ❒ 문제 분석 누적 합을 관리해 줄 변수(accumulate)가 필요하다. 우선 주어진 트리에서 값이 가장 큰 노드를 찾아야 한다. (오른쪽 서브트리를 탐색)accumulate에 현재 노드의 값을 갱신해준다. (덧셈)현재 노드의 왼쪽 서브트리를 탐색한다.2~3번 과정을 반복한다. 위 그림에서 작업 순서는 9 > 7 > 6 > 5 > 4 > 3 > 2 > 1 > 0 이 된다.     ❒ Solution..

❒ Description날짜2024.09.25 (수)레벨Easy제목Convert Sorted Array to Binary Search Tree링크https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/자료구조그래프 - BST시간 복잡도O(n)이번 문제는 BST의 특징을 정확하게 파악하고 있어야 한다.     ❒ Solutionpublic TreeNode sortedArrayToBST(int[] nums) { return construct(nums, 0, nums.length - 1);}public TreeNode construct(int[] nums, int lo, int hi) { if (lo >..

❒ Description날짜2024.09.23 (월)레벨Medium제목Minimum Height Trees링크https://leetcode.com/problems/minimum-height-trees/description/자료구조그래프시간복잡도O(N)     ❒ 문제 분석이 문제는 트리의 리프 노드에서부터 루트로 다가가며 해결해야 한다. 여기서는 차수가 1인 리프노드를 제거하면서 루트로 다가가야 한다. 가장 낮은  차수를 제거하는 방식은 위상 정렬과 유사한 방식으로 해석할 수 있다. ※ 차수(degree) : 각 노드가 가진 서브트리의 갯수    ❒ Solution1. 리프노드를 제거하는 방법더보기더보기public List findMinHeightTrees(int n, int[][] edges) { ..

❒ Description날짜2024.09.22 (일)레벨Easy제목Balanced Binary Tree링크https://leetcode.com/problems/balanced-binary-tree/description/자료구조그래프시간 복잡도O(N) 이번 문제를 풀기 위해서는 Height-Balanced Binary Tree에 대한 이해가 필요하다.     ❒ Solutionpublic void isBalanced(TreeNode root) { return depth(root) != -1;}public int depth(TreeNode node) { if (node == null) return 0; int left = depth(node.left); int right = depth(..

❒ Description날짜2024.09.22 (토)레벨Easy제목Invert Binary Tree링크https://leetcode.com/problems/invert-binary-tree/자료구조그래프알고리즘X시간 복잡도O(n) 이번 문제는 재귀구조를 연습할 수 있는 좋은 문제였다. 다양한 풀이 방법을 통해 재귀에 익숙해지자.     ❒ Solution1. 새로운 노드 생성 DFSpublic invertTree(TreeNode root) { if (root == null) return null; // 1. 새로운 노드 생성 TreeNode inverted = new TreeNod(root.val); // 2. 새로운 노드의 left, right 설정 invert..

❒ Description날짜2024.09.21 (토)레벨Medium제목Longest Univalue Path링크https://leetcode.com/problems/longest-univalue-path/submissions/1397321235/자료구조트리알고리즘X시간 복잡도O(n) 543. Diameter of Binary Tree와 굉장히 유사한 문제이다.     ❒ 문제 분석부모-노드의 value와 자식-노드의 value가 동등한지를 판단하여야 하는 문제이다. 이 문제 또한 재귀를 통해 Left, Right 자식 트리의 깊이를 파악함과 동시에 가장 긴 경로를 파악해야 한다.위 그림에서 리프노드의 1과 1은 부모노드의 값인 4와 동일하지 못하기 때문에 문제의 요구사항에 충족하지 못한다.     ❒ S..

❒ Description레벨Easy날짜2024.09.19 (목)제목Assign Cookies링크https://leetcode.com/problems/assign-cookies/description/자료구조배열알고리즘그리디시간 복잡도O(NlogN)     ❒ 문제 분석우선 각 배열의 의미를 잘 이해해야 한다.g 배열 : i번 째 아이들를 만족시킬 수 있는 쿠키의 크기들의 집합i 배열 : 각 쿠키의 크기를 나타낸 집합예를 들어 g = {1, 2, 3}, s = {1, 1} 이라면 최대 1명의 아이만 만족할 수 있다.s[1]은 g[1]을 만족시킬 수 있다.s[2]은 g[2]을 만족시킬 수 없다.s[2]은 g[3]을 만족시킬 수 없다.     ❒ Solutionpublic int findContentChildr..