728x90 반응형 tree15 145. Binary Tree Postorder Traversal 이진 트리를 후위 순회(postorder traversal)하는 방법을 구현하는 문제입니다. 문제 설명: 주어진 이진 트리를 후위 순회(postorder traversal)하는 방법은 다음과 같습니다: 왼쪽 서브트리를 후위 순회합니다. 오른쪽 서브트리를 후위 순회합니다. 루트 노드를 방문합니다. 후위 순회는 왼쪽 서브트리와 오른쪽 서브트리를 모두 순회한 후에 루트 노드를 방문하는 순서입니다. 예를 들어, 다음과 같은 이진 트리가 주어진 경우: 1 / \ 2 3 / \ 4 5 후위 순회(postorder traversal)는 다음과 같은 순서로 노드를 방문합니다: 4 -> 5 -> 2 -> 3 -> 1 후위 순회를 구현하기 위해 재귀 함수를 사용하거나 스택을 활용할 수 있습니다. public class S.. 2023. 11. 5. 110. Balanced Binary Tree 주어진 이진 트리가 균형 잡힌 트리인지 확인하세요. 균형 잡힌 트리는 모든 서브트리의 높이 차이가 1 이하인 트리를 의미합니다. 즉, 모든 서브트리가 높이 균형을 유지하고 있는 경우 균형 잡힌 트리입니다. 예를 들어, 다음은 균형 잡힌 트리입니다: 3 / \ 9 20 / \ 15 7 각 서브트리의 높이 차이가 1 이하입니다. 반면에, 다음 트리는 균형 잡힌 트리가 아닙니다: 1 / \ 2 2 / \ 3 3 / \ 4 4 여기서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 2이므로 균형 잡힌 트리가 아닙니다. 균형 잡힌 트리 여부를 판단하기 위해, 주어진 트리의 각 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이를 비교하여 높이 차이가 1 이하인지 확인해야 합니다. 이 작업을 트리의 모든 노드에 대해 재.. 2023. 11. 4. 101. Symmetric Tree 이진 트리가 대칭 구조인지 여부를 판단하는 문제입니다. 대칭 구조는 트리가 좌우 대칭인지를 의미합니다. 즉, 루트 노드를 중심으로 좌우 하위 트리가 대칭인 경우에 대칭 트리입니다. 문제 설명: 주어진 이진 트리가 대칭 구조인지 판단하세요. 이진 트리의 대칭 구조는 다음과 같이 정의됩니다: 루트 노드가 비어있으면 (null이면) 대칭입니다. 루트 노드가 비어있지 않다면, 좌우 서브트리가 대칭이어야 합니다. 좌우 서브트리의 대칭 여부는 다음과 같이 판단됩니다: 두 서브트리의 루트 노드 값이 동일해야 합니다. 왼쪽 서브트리의 왼쪽 서브트리와 오른쪽 서브트리의 오른쪽 서브트리가 대칭이어야 합니다. 왼쪽 서브트리의 오른쪽 서브트리와 오른쪽 서브트리의 왼쪽 서브트리가 대칭이어야 합니다. 예시: 다음은 대칭 트리와 .. 2023. 11. 1. 108. Convert Sorted Array to Binary Search Tree 주어진 정렬된 정수 배열을 사용하여 균형 잡힌 이진 검색 트리(Binary Search Tree)를 만드는 문제입니다. 아래는 문제의 자세한 설명입니다: 문제 설명: 주어진 정렬된 정수 배열 nums를 사용하여 높이 균형을 갖는 이진 검색 트리를 생성하세요. 이진 검색 트리는 다음과 같은 조건을 만족해야 합니다: 노드의 왼쪽 서브 트리에는 해당 노드보다 작은 값의 노드들만 포함되어야 합니다. 노드의 오른쪽 서브 트리에는 해당 노드보다 큰 값의 노드들만 포함되어야 합니다. 각 서브 트리도 이진 검색 트리여야 합니다. 예시: 주어진 nums 배열이 [1, 2, 3]라면, 다음과 같은 이진 검색 트리를 생성해야 합니다: 2 / \ 1 3 노트: nums 배열의 길이는 1 이상 10^4 이하입니다. nums 배.. 2023. 10. 25. Binary Search Tree : Insertion BST에 노드를 삽입하는 과정은 다음과 같습니다: 루트 노드부터 시작합니다. 현재 노드의 값과 삽입하려는 데이터 값을 비교합니다. 삽입하려는 데이터 값이 현재 노드의 값보다 작으면 왼쪽 서브트리로 이동하고, 값이 크면 오른쪽 서브트리로 이동합니다. 만약 해당 서브트리가 비어있으면 새로운 노드를 생성하고 그 위치에 삽입합니다. 만약 해당 서브트리가 비어있지 않다면 서브트리의 루트로 이동하여 2단계부터 반복합니다. 모든 작업이 완료되면 변경된 BST의 루트 노드를 반환합니다. BST에 노드를 삽입하는 이 과정을 재귀적으로 구현하거나 반복문을 사용하여 구현할 수 있습니다. 주어진 문제에서는 이 과정을 잘 구현하여 새로운 노드를 BST에 삽입하고 변경된 BST의 루트 노드를 반환하는 함수를 작성해야 합니다. N.. 2023. 10. 6. Tree: Level Order Traversal 이진 트리를 레벨 순서(또는 너비 우선)로 순회하고, 각 레벨의 노드 값을 순차적으로 출력하는 문제입니다. 이 문제는 이진 트리를 레벨마다 순회하여 레벨 별로 노드 값을 출력하는 방법을 구현하는 것이 목표입니다. 레벨 순서 순회(Level Order Traversal)란 루트 노드에서부터 시작하여 레벨 1부터 차례대로 아래로 내려가며 노드를 방문하는 방법입니다. 각 레벨에서 왼쪽에서 오른쪽 순서로 노드를 방문합니다. 즉, 레벨 1의 노드를 모두 방문한 후에 레벨 2의 노드를 방문하고, 레벨 2의 노드를 모두 방문한 후에 레벨 3의 노드를 방문하는 식으로 계속 진행됩니다. 문제의 입력으로는 이진 트리가 주어지며, 출력으로는 레벨 순서 순회 결과인 노드 값들을 순차적으로 반환하는 것이 요구됩니다. 이를 위해.. 2023. 10. 5. Tree : Top View 이진 트리의 "상단 뷰"를 찾는 문제입니다. 상단 뷰란 이진 트리를 위에서 아래로 내려다 볼 때, 가장 왼쪽 노드부터 가장 오른쪽 노드까지 순서대로 보이는 노드들의 값을 출력하는 것을 의미합니다. 상단 뷰를 찾기 위해서는 이진 트리의 루트 노드에서 시작하여 왼쪽으로 이동할 때는 왼쪽 자식 노드로, 오른쪽으로 이동할 때는 오른쪽 자식 노드로 이동하면서 노드들의 값을 출력해야 합니다. 이 때, 같은 수평 레벨에 여러 노드가 있는 경우에는 가장 왼쪽 노드를 출력해야 합니다. 문제의 목표는 주어진 이진 트리에서 상단 뷰에 있는 노드들의 값을 순서대로 출력하는 것 BFS(Breadth-First Search) 알고리즘을 사용하여 풀 수 있습니다. BFS를 사용하면 각 노드의 수평 거리를 추적할 수 있으며, 각 수.. 2023. 10. 5. 이전 1 2 3 다음 728x90 반응형