이진 트리 중위 순회 (Binary Tree Inorder Traversal) 풀이
이진 트리의 root가 주어졌을 때, 노드 값들을 중위 순회(inorder traversal)한 결과를 반환하세요.
예시 1:
입력: root = [1,null,2,3]
출력: [1,3,2]
설명:
예시 2:
입력: root = [1,2,3,4,5,null,8,null,null,6,7,9]
출력: [4,2,6,5,7,1,3,9,8]
설명:
예시 3:
입력: root = []
출력: []
예시 4:
입력: root = [1]
출력: [1]
제약 조건:
•
트리의 노드 개수는 0 이상 100 이하입니다.
•
-100 <= Node.val <= 100
추가 과제:
재귀 풀이가 가장 쉽습니다. 반복문으로도 구현할 수 있나요?
이진 트리 지그재그 레벨 순회 (Binary Tree Zigzag Level Order Traversal) 풀이
이진 트리의 root가 주어졌을 때, 노드 값들을 지그재그 형태로 레벨 순회(level order traversal)한 결과를 반환하세요.
(즉, 한 레벨은 왼쪽에서 오른쪽으로, 다음 레벨은 오른쪽에서 왼쪽으로 번갈아 가며 순회합니다.)
예시 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]
Plain Text
복사
예시 2:
Input: root = [1]
Output: [[1]]
Plain Text
복사
예시 3:
Input: root = []
Output: []
Plain Text
복사
제약 조건:
•
트리의 노드 개수는 0 이상 2000 이하입니다.
•
-100 <= Node.val <= 100
전위/중위 순회로 이진 트리 구성 (Construct Binary Tree from Preorder and Inorder Traversal) 풀이
정수 배열 preorder(전위 순회)와 inorder(중위 순회)가 주어집니다. 두 배열은 같은 이진 트리를 서로 다른 순회 방식으로 나타낸 것입니다.
이때 해당 이진 트리를 구성하여 반환하세요.
예시 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
Plain Text
복사
예시 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
Plain Text
복사
제약 조건:
•
1 <= preorder.length <= 3000
•
inorder.length == preorder.length
•
-3000 <= preorder[i], inorder[i] <= 3000
•
preorder와 inorder는 서로 다른(unique) 값으로 구성됩니다.
•
inorder의 각 값은 preorder에도 등장합니다.
•
preorder는 해당 트리의 전위 순회 결과임이 보장됩니다.
•
inorder는 해당 트리의 중위 순회 결과임이 보장됩니다.
각 노드의 다음 오른쪽 포인터 채우기 (Populating Next Right Pointers in Each Node) 풀이
모든 리프가 같은 레벨에 있고, 모든 부모가 두 자식을 가지는 완전한(Perfect) 이진 트리가 주어집니다.
트리 노드 정의는 다음과 같습니다.
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Plain Text
복사
각 노드의 next 포인터가 같은 레벨의 바로 오른쪽 노드를 가리키도록 설정하세요.
오른쪽 노드가 없다면 next는 NULL이 되어야 합니다.
처음에는 모든 next 포인터가 NULL로 설정되어 있습니다.
예시 1:
Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: 위의 완전 이진 트리(그림 A)에서, 각 노드의 next를 같은 레벨의 다음 노드로 연결하면 그림 B와 같아집니다.
직렬화된 출력은 next 포인터로 연결된 상태를 레벨 순서로 나타내며, '#'는 각 레벨의 끝을 의미합니다.
Plain Text
복사
예시 2:
Input: root = []
Output: []
Plain Text
복사
제약 조건:
•
트리의 노드 개수는 0 이상 2^12 - 1 이하입니다.
•
-1000 <= Node.val <= 1000
추가 과제:
•
추가 공간을 상수(constant) 만큼만 사용하세요.
•
재귀 방식은 허용합니다. (암묵적인 호출 스택은 추가 공간으로 치지 않는다고 가정합니다.)
BST에서 k번째로 작은 원소 (Kth Smallest Element in a BST) 풀이
이진 탐색 트리(BST)의 root와 정수 k가 주어질 때, 트리의 모든 노드 값 중 k번째로 작은 값( 1부터 시작 )을 반환하세요.
예시 1:
Input: root = [3,1,4,null,2], k = 1
Output: 1
Plain Text
복사
예시 2:
Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
Plain Text
복사
제약 조건:
•
노드 개수는 n입니다.
•
1 <= k <= n <= 10^4
•
0 <= Node.val <= 10^4
추가 과제:
BST가 자주 변경(삽입/삭제)되고, k번째 원소를 자주 찾아야 한다면 어떻게 최적화할 수 있을까요?
BST에서 중위 순회 후계자 (Inorder Successor in BST)
이진 탐색 트리(BST)와 그 안의 어떤 노드가 주어졌을 때, 해당 노드의 중위 순회(in-order) 후계자(successor)를 찾으세요.
노드 p의 successor는 p.val보다 큰 값들 중에서 가장 작은 값을 가진 노드입니다.
예시 1:
Input: root = [2,1,3], p = 1
Output: 2
Explanation: 1의 중위 순회 후계자는 2입니다. p와 반환값은 모두 TreeNode 타입입니다.
Plain Text
복사
예시 2:
Input: root = [5,3,6,2,4,null,null,1], p = 6
Output: null
Explanation: 현재 노드의 후계자가 없으므로 정답은 null입니다.
Plain Text
복사
참고:
1.
주어진 노드에 중위 순회 후계자가 없다면 null을 반환합니다.
2.
트리의 값들은 모두 서로 다릅니다.
섬의 개수 (Number of Islands) 풀이
m x n 크기의 2차원 문자 그리드 grid가 주어집니다. 각 칸은 '1'(땅) 또는 '0'(물)입니다.
상하좌우로 인접한 땅들이 연결되어 하나의 섬(island) 을 이룹니다.
그리드의 네 변은 모두 물로 둘러싸여 있다고 가정할 때, 섬의 개수를 반환하세요.
예시 1:
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
Plain Text
복사
예시 2:
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
Plain Text
복사
제약 조건:
•
m == grid.length
•
n == grid[i].length
•
1 <= m, n <= 300
•
grid[i][j]는 '0' 또는 '1'입니다.