Java에서 이진 트리의 최대 깊이를 찾는 방법(코드 포함)

이 기사의 내용은 Java에서 (코드 포함) 이진 트리의 최대 깊이를 찾는 방법에 대한 것입니다. 이는 특정 참조 값을 가지고 있으므로 도움이 될 수 있습니다.

이진 트리가 주어지면 최대 깊이를 구하세요.

이진 트리의 깊이는 루트 노드에서 가장 먼 리프 노드까지의 가장 긴 경로에 있는 노드 수입니다.

설명: 리프 노드는 하위 노드가 없는 노드를 나타냅니다.

예:
이진 트리 [3,9,20,null,null,15,7],

3
/
9 20
/
15 7

은 최대 깊이 3을 반환합니다.

이 질문을 통해 트리의 사용법을 익히세요

질문 분석: 이진 트리의 깊이를 알아보세요.

이진 트리의 기본 개념을 한눈에 찾아볼 수 있습니다.

우리는 동일합니다 재귀적 방법을 사용하여 이 문제를 해결합니다. 루트 노드가 비어 있지 않으면 왼쪽 하위 트리와 오른쪽 하위 트리를 재귀적으로 순회하여 어떤 하위 트리에 더 많은 레이어가 있는지 확인하고 마지막으로 리프까지 순회합니다. 노드에 도달했습니다.

다음 문을 사용하여 능숙하게 구현하세요. return nleft > nright ? nright + 1;

다음 이진 트리를 예로 들어보세요. 3 /

9 20

/
15 7


1. 이 트리는 비어 있지 않습니다.

2. 이 트리의 왼쪽 하위 트리를 재귀적으로 탐색합니다. 왼쪽 하위 트리와 왼쪽 하위 트리 모두 비어 있지 않습니다. 왼쪽 하위 트리의 오른쪽 하위 트리가 비어 있으면 모두 0을 반환하고 판단합니다. 0 == 0이면 이 트리의 왼쪽 하위 트리는 0 + 1 = 1을 반환합니다.

3. : 오른쪽 하위 트리는 비어 있지 않습니다. 오른쪽 하위 트리의 왼쪽 하위 트리와 오른쪽 하위 트리는 오른쪽 하위 트리의 왼쪽 하위 트리와 왼쪽 하위 트리의 오른쪽 하위 트리를 재귀적으로 순회합니다. 오른쪽 하위 트리가 비어 있으면 0을 반환합니다. 오른쪽 하위 트리의 오른쪽 하위 트리의 왼쪽 하위 트리와 오른쪽 하위 트리가 비어 있으면 0을 반환하고 판단합니다. 0 == 0이면 오른쪽 하위 트리의 왼쪽 하위 트리와 오른쪽 하위 트리가 됩니다. 이 트리의 0 + 1 = 1을 반환하고 1 == 1을 반환하면 이 트리의 오른쪽 하위 트리는 1 + 1 = 2를 반환합니다.

4. 그러면 이 트리는 2 + 1 = 3을 반환하고 이 트리의 깊이, 즉 레이어 수는 3입니다.

사실 이 방법의 주요 아이디어는 다음과 같습니다. 이 트리의 리프 노드로 가는 길, 그리고 마지막으로 리프 노드에서 시작합니다. 루트 노드까지 역추적하여 +1하면 결과는 +1로 전달된 경로의 길이입니다.

코드 구현:

public static class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;
        TreeNode(int val)
        {
            data = val;
        }
    }

    public int maxDepth(TreeNode root)
    {
        if (root == null)
            return 0;

        int nleft = maxDepth(root.left);
        int nright = maxDepth(root.right);

        return nleft > nright ? nleft + 1 : nright + 1;
    }

주요 기능:

public static void main(String[] args)
    {
        TreeNode p = new TreeNode(1);
        p.left = new TreeNode(2);
        p.right = new TreeNode(3);
        p.left.left = null;
        p.left.right = null;
        p.right.left = new TreeNode(4);
        p.right.right = new TreeNode(5);

        Tree1 t = new Tree1();
        System.out.println(t.maxDepth(p));
    }

실행 결과: 3

위 내용은 Java에서 이진 트리의 최대 깊이를 찾는 방법(코드 포함)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!