문제 설명
이진 트리의 루트 노드(root)가 주어졌을 때, 트리의 최대 깊이를 반환하세요.
이진 트리의 최대 깊이는 루트 노드에서부터 **가장 먼 리프 노드(leaf node)**까지의 경로에 있는 노드의 수를 의미합니다.
예시
예시 1:
입력: root = [3, 9, 20, null, null, 15, 7]
출력: 3
Plain Text
복사
설명:
이진 트리는 아래와 같습니다.
3
/ \
9 20
/ \
15 7
Plain Text
복사
가장 깊은 경로는 3 → 20 → 15 또는 3 → 20 → 7로 깊이는 3입니다.
예시 2:
입력: root = [1, null, 2]
출력: 2
Plain Text
복사
설명:
1
\
2
Plain Text
복사
깊이는 2입니다.
제한 사항
•
트리의 노드 수는 0 이상 10,000 이하입니다.
•
각 노드의 값은 100 이상 100 이하입니다.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution
{
public:
int maxDepth(TreeNode* root)
{
}
};
C++
복사
유효한 이진 탐색 트리 (Validate Binary Search Tree)
문제 설명
이진 트리의 루트 노드(root)가 주어졌을 때, **해당 트리가 유효한 이진 탐색 트리(BST)**인지 판별하세요.
유효한 BST의 정의:
•
왼쪽 서브트리에 있는 모든 노드는 해당 노드의 값보다 작아야 합니다.
•
오른쪽 서브트리에 있는 모든 노드는 해당 노드의 값보다 커야 합니다.
•
왼쪽, 오른쪽 서브트리 모두 각각 유효한 이진 탐색 트리여야 합니다.
예시
예시 1:
입력: root = [2, 1, 3]
출력: true
Plain Text
복사
이 트리는 아래와 같으며, 모든 노드가 BST 조건을 만족합니다.
예시 2:
입력: root = [5, 1, 4, null, null, 3, 6]
출력: false
Plain Text
복사
이 트리는 아래와 같습니다:
문제점: 4는 5의 오른쪽 자식이므로 > 5여야 하지만, 4의 왼쪽 자식인 3은 5보다 작아서 BST 조건을 위반합니다.
따라서 결과는 false입니다.
제한 사항
•
트리의 노드 수는 1 이상 10,000 이하입니다.
•
각 노드의 값은 2³¹ 이상 2³¹ - 1 이하입니다.
대칭 트리 (Symmetric Tree)
문제 설명
이진 트리의 루트 노드(root)가 주어졌을 때, 해당 트리가 자기 자신을 중심으로 대칭적인지 확인하세요.
즉, 트리가 자신의 거울 이미지인지를 검사합니다.
대칭 트리의 정의
•
트리의 왼쪽 서브트리와 오른쪽 서브트리가 좌우 반전된 거울 이미지여야 합니다.
•
구체적으로:
◦
왼쪽 자식의 왼쪽 오른쪽 자식의 오른쪽
오른쪽 자식의 오른쪽◦
왼쪽 자식의 오른쪽 오른쪽 자식의 왼쪽
오른쪽 자식의 왼쪽 예시
예시 1:
입력: root = [1, 2, 2, 3, 4, 4, 3]
출력: true
Plain Text
복사
구조:
1
/ \
2 2
/ \ / \
3 4 4 3
Plain Text
복사
→ 완벽하게 좌우 대칭입니다. 결과는 true.
예시 2:
입력: root = [1, 2, 2, null, 3, null, 3]
출력: false
Plain Text
복사
구조:
1
/ \
2 2
\ \
3 3
Plain Text
복사
→ 좌우 구조가 대칭이 아니므로 결과는 false.
제한 사항
•
노드 수: 1 이상 1,000 이하
•
노드 값: 100 이상 100 이하
추가 과제 (Follow-up)
재귀적 방식과 반복적 방식(큐 이용) 모두로 풀 수 있나요?
•
재귀적 방식: 두 노드를 비교하면서 각각의 자식 노드들을 재귀 호출로 검사
•
반복적 방식: 큐를 사용하여 좌우 쌍을 하나씩 꺼내면서 비교
이진 트리의 레벨 순회 (Binary Tree Level Order Traversal)
문제 설명
이진 트리의 루트 노드 root가 주어졌을 때, 노드의 값을 레벨 순서대로 (왼쪽에서 오른쪽으로) 반환하세요.
즉, 트리를 층별로 왼쪽 → 오른쪽 순서로 방문합니다.
예시
예시 1:
입력: root = [3, 9, 20, null, null, 15, 7]
출력: [[3], [9, 20], [15, 7]]
Plain Text
복사
트리 구조:
3
/ \
9 20
/ \
15 7
Plain Text
복사
→ 1층: [3]
→ 2층: [9, 20]
→ 3층: [15, 7]
예시 2:
입력: root = [1]
출력: [[1]]
Plain Text
복사
예시 3:
입력: root = []
출력: []
Plain Text
복사
제한 사항
•
노드 수: 0 이상 2,000 이하
•
노드 값: 1000 이상 1000 이하
구현 팁
이 문제는 BFS (너비 우선 탐색) 으로 해결할 수 있습니다.
→ queue를 사용해 각 층의 노드들을 순차적으로 탐색하면서 결과 리스트에 추가합니다.
정렬된 배열을 높이 균형 이진 탐색 트리로 변환 (Convert Sorted Array to Binary Search Tree)
문제 설명
오름차순으로 정렬된 정수 배열 nums가 주어졌을 때,
이를 높이 균형(height-balanced) 이진 탐색 트리(BST)로 변환하세요.
높이 균형 BST란?
•
모든 노드에 대해 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하인 트리입니다.
•
즉, 트리의 구조가 한쪽으로 치우치지 않아야 합니다.
예시
예시 1:
입력: nums = [-10, -3, 0, 5, 9]
출력: [0, -3, 9, -10, null, 5]
Plain Text
복사
트리 구조 예시:
0
/ \
-3 9
/ /
-10 5
Plain Text
복사
[0, -10, 5, null, -3, null, 9]과 같이 구조만 높이 균형이라면 순서가 다소 달라도 정답으로 인정됩니다.
예시 2:
입력: nums = [1, 3]
출력: [3, 1]
Plain Text
복사
가능한 트리 구조:
3
/
1
Plain Text
복사
또는
1
\
3
Plain Text
복사
→ 둘 다 균형 잡힌 BST입니다.
제한 사항
•
1 <= nums.length <= 10,000
•
10⁴ <= nums[i] <= 10⁴
•
nums는 중복 없이 오름차순 정렬되어 있습니다.
구현 아이디어
•
이진 탐색 트리 + 균형 잡힘 → 항상 중간 값을 루트로 선택!
•
재귀적으로 배열을 좌/우 분할해 트리 구성
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution
{
public:
TreeNode * sortedArrayToBST(vector<int>& nums)
{
}
};
C++
복사
