본문 바로가기

Algorithm20

173. Binary Search Tree Iterator 문제 왼쪽, 오른쪽 포인터를 가지고 있는 TreeNode 클래스를 생성자 파라미터로 전달받아 next(), hasNext() 메소드 기능을 가지고 있는 BSTIterator 라는 클래스를 구현하는 문제입니다. next() 메소드는 in-order 방식으로 순회했을때 다음 원소를 리턴하고, hasNext() 메소드는 in-order 방식으로 순회했을때 다음 원소가 있으면 true, 없으면 false 를 리턴해야합니다. 문제 풀이 코드 class BSTIterator { List list; int index = 0; public BSTIterator(TreeNode root) { list = new ArrayList(); inorderToList(root); } private void inorderToLis.. 2023. 12. 30.
129. Sum Root to Leaf Numbers 문제 Linked List 로 구현된 이진 트리가 주어졌을때, 루트 노드 부터 리프 노드까지 순회하면서 전체 노드의 총 합을 구하는 문제입니다. 그런데 아래 그림에 나온 설명처럼, 루트노드 부터 리프노드 까지의 숫자를 단순히 sum 하는것이 아닌 string 형태로 합친 후 sum 을 해야합니다. 문제 풀이 미디엄 문제 치고는 간단한 문제입니다. 전체 노드를 전위순회(pre order) 하기만 하면서 sum 을 해주면 풀립니다. 문제 풀이 코드 static int sum = 0; public static int sumNumbers(TreeNode root) { preorder(root, ""); return sum; } private static void preorder(TreeNode root, Str.. 2023. 12. 29.
114. Flatten Binary Tree to Linked List 문제 Linked List 로 구성된 이진트리가 주어졌을때, 모든 노드들을 오른쪽 노드로 옮기고, 왼쪽 노드는 null 로 만드는 문제입니다. 문제 풀이 루트 노드의 오른쪽 노드를 왼쪽 노드의 오른쪽 자식 노드로 합친 뒤에 합쳐진 노드를 오른쪽으로 옮기면 됩니다. 1. 루트 노드의 왼쪽 자식 노드가 있으면 왼쪽 자식 노드의 가장 마지막 오른쪽 자식 노드를 찾습니다. 2. 가장 마지막 자식 노드에 루트 노드의 오른쪽 자식 노드를 이어 붙입니다. 3. 루트 노드의 왼쪽 자식 노드를 오른쪽 자식 노드로 옮겨주고, 왼쪽 노드는 null 처리합니다. 4. 루트노드의 포인터를 오른쪽 자식 노드로 옮기면서 1~3번을 반복합니다. 문제 풀이 코드를 보면 아래와 같습니다. 문제 풀이 코드 private void flat.. 2023. 12. 29.
106. Construct Binary Tree from Inorder and Postorder Traversal 문제 중위순회(inorder), 후위순회(postorder) 값이 int[] 형 배열로 주어졌을때 이진트리를 만드는 문제입니다. int[] inorder = {9, 3, 15, 20, 7}; int[] postorder = {9, 15, 7, 20, 3}; result = [3, 9, null, null, 20, 15, 7] 문제 풀이 기존 105번 문제와 동일하지만 preorder 값 대신 postorder 가 주어집니다. https://moonstorage.tistory.com/10 105. Construct Binary Tree from Preorder and Inorder Traversal 문제 int[] 형 배열로 전위순회(preorder), 중위순회(inorder) 값이 주어졌을때 Binary.. 2023. 12. 27.

티스토리툴바