트리 데이터 구조의 높이
이 자습서에서는 이진 트리에 대해 설명합니다. 우리는 재귀적으로 뿐만 아니라 반복적으로 트리 데이터 구조의 높이를 계산하는 방법을 볼 것입니다.
이진 트리
- 재귀 방식
- 반복적인 방식
트리 높이 - 재귀적으로
재귀는 하위 문제의 결과를 계산하고 상위 문제로 다시 반환하는 것을 포함합니다.
관련 단계:
- 트리의 높이를 재귀적으로 계산하려면 왼쪽 하위 트리와 오른쪽 하위 트리의 높이를 재귀적으로 찾아 1을 더해야 합니다(최상위 노드와 자식 사이의 높이).
- 이러한 각 하위 트리는 왼쪽 및 오른쪽 하위 트리를 가질 수 있으므로 하위 트리가 NULL이 될 때까지 재귀가 적용됩니다. 널 트리 노드의 높이는 -1입니다.
- 마지막으로 왼쪽 및 오른쪽 하위 트리의 높이를 비교하고 더 큰 것을 반환합니다.
package com.journaldev.tree.height;
public class BinaryTree {
TreeNode root;
public static class TreeNode {
TreeNode left;
TreeNode right;
Object data;
TreeNode(Object data) {
this.data = data;
left = right = null;
}
}
}
재귀를 사용하여 트리의 높이를 찾는 코드를 살펴보겠습니다.
package com.journaldev.tree.height;
import com.journaldev.tree.height.BinaryTree.TreeNode;
public class HeightOfTree {
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
/**
* Binary Tree in our example, height = 2
* 1 (Root)
* 2 3 (Level 1)
* 4 5 (Level 2)
*/
binaryTree.root = new TreeNode(1);
binaryTree.root.left = new TreeNode(2);
binaryTree.root.right = new TreeNode(3);
binaryTree.root.left.left = new TreeNode(4);
binaryTree.root.right.left = new TreeNode(5);
int heightOfTree = height(binaryTree.root);
System.out.printf("Height of tree is %d", heightOfTree);
}
public static int height(TreeNode root) {
if (root == null)
return -1;
int leftHeight = height(root.left);
int rightHeight = height(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
}
따라서 위의 코드에서 맨 아래 자식 노드에 도달하면 트리 높이에 1을 추가하고 그 결과를 이전 호출에 반환합니다. 출력: 트리의 높이는 2입니다. 이제 동일한 작업을 비재귀적으로 수행해 보겠습니다.
트리 높이 - 반복적으로
트리의 높이를 반복적으로 계산하려면 트리의 레벨 수를 계산하기만 하면 됩니다.
관련 단계
- 대기열을 만들고 여기에 트리의 루트를 추가합니다.
- 대기열에서 노드를 팝하고 하위 노드를 대기열에 추가하는 동안 대기열을 탐색합니다.
- 각 반복에서 최신 요소가 대기열에 추가되고 이 요소의 다음 수준 요소가 대기열에 추가됩니다.
- 대기열 크기가 0이 될 때까지 이 작업을 수행합니다. 이는 다음 레벨에 요소가 없음을 의미합니다.
- 이동한 모든 레벨에 대해 1을 추가합니다.
다음은 나무의 높이를 계산하는 반복 프로그램입니다.
public static int heightIteratively(TreeNode root) {
if (root == null)
return -1;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int height = -1;
while (!queue.isEmpty()) {
int size = queue.size();
height++;
while (size > 0) {
TreeNode treeNode = queue.remove();
if (treeNode.left != null)
queue.add(treeNode.left);
if (treeNode.right != null)
queue.add(treeNode.right);
size--;
}
}
return height;
}
시간 복잡도는 O(n)입니다. 공간 복잡도는 O(1)입니다.
GitHub 리포지토리에서 전체 코드와 더 많은 DS 및 알고리즘 예제를 체크아웃할 수 있습니다.