N 항 트리 Leetcode 솔루션의 최대 깊이

난이도 쉽게
자주 묻는 질문 아마존 구글 Microsoft
알고리즘 폭 우선 검색 코딩 깊이 우선 검색 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions N 항 트리조회수 32

이 문제에서 우리는 N 항 트리즉, 노드가 2 개 이상의 자식을 가질 수 있도록하는 트리입니다. 나무 뿌리에서 가장 먼 잎의 깊이를 찾아야합니다. 이를 최대 수심이라고합니다. 경로의 깊이는 경로의 노드 수입니다.

       2

  /    |    \

3      4      6

                \
           
                  9
3

설명: 값이 9 인 잎은 뿌리에서 가장 멀고 깊이는 3. 그래서 우리는 3을 인쇄합니다.

      2
  
  /      \

3           6   

        /   |   \

      4     7     9
3

설명: 값이 4,7 및 9 인 잎은 뿌리에서 가장 멀고 깊이는 3. 그래서 우리는 3을 인쇄합니다.

접근하다(재귀)

이진 트리의 최대 깊이는 노드의 왼쪽 및 오른쪽 자식에서 재귀 함수를 호출하여 계산됩니다. 마찬가지로 N 항 트리의 경우 모든 노드의 모든 자식에 대해 재귀 함수를 호출하여 최대 깊이를 계산할 수 있습니다. 이 접근 방식은 재귀 적이며 트리의 단일 패스 만 필요합니다.

N 항 트리 Leetcode 솔루션의 최대 깊이

암호알고리즘

  1. 함수 만들기 maxDepth () 트리의 최대 깊이를 반환합니다. 뿌리 그것에 전달됩니다
  2. If 뿌리 null 인 경우 :
    • 0를 반환
  3. 변수 초기화 최대 깊이 N 항 트리의 최대 깊이 저장
  4. 매회마다 아이 현재 루트의 자식 목록에서 :
    • 세트 maximumDepth = max (maxDepth (root.left), maxDepth (root.right))
  5. 반환 최대 깊이 + 1

N-ary Tree Leetcode 솔루션의 최대 깊이 구현

C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

struct Node
{
    int value;
    vector <Node*> children;

    Node(int val)
    {
        value = val;
        children = {};
    }

    Node(int val , vector <Node*> childList)
    {
        value = val;
        children = childList;
    }
};

int maxDepth(Node* root)
{
    if(root == NULL)
        return 0;
    int maximumDepth = 0;
    for(Node* &child : root->children)
        maximumDepth = max(maximumDepth , maxDepth(child));
    return maximumDepth + 1;
}

int main()
{
    Node* root = new Node(2);
    root->children = {new Node(3) , new Node(4) , new Node(5)};
    root->children[2]->children = {new Node(9)};
    cout << maxDepth(root) << '\n';
    return 0;
}

자바 프로그램

import java.lang.Math;

class Node
{
    int value;
    Node[] children;

    Node(int val)
    {
        value = val;
        children = new Node[]{};
    }

    Node(int val , Node[] childList)
    {
        value = val;
        children = childList;
    }
};

class maximum_depth
{
    public static void main(String args[])
    {
        Node root = new Node(2);
        Node[] a = {new Node(3) , new Node(4) , new Node(5)};
        root.children = a;
        Node[] b = {new Node(9)};
        root.children[2].children = b;
        System.out.println(maxDepth(root));
    }

    static int maxDepth(Node root)
    {
        if(root == null)
            return 0;
        int maximumDepth = 0;
        for(int i = 0 ; i < root.children.length ; i++)
            maximumDepth = Math.max(maximumDepth , maxDepth(root.children[i]));
        return maximumDepth + 1;
    }
}
3

N-ary Tree Leetcode 솔루션의 최대 깊이에 대한 복잡성 분석

시간 복잡성

O (N), N = 전체 트리를 한 번 횡단 할 때 N 항 트리의 크기.

공간 복잡성

의 위에) 재귀 호출을 위해 메모리에 스택 프레임을 저장하기 때문입니다.

접근하다(반복적 인)

스택 또는 큐를 사용하여 루트에서 노드와 해당 깊이를 저장하여 위의 프로세스를 반복적으로 수행 할 수 있습니다. 최대 깊이는이 과정에서 얻은 모든 뿌리의 최대 깊이입니다. 이를 위해 큐를 사용하고 트리의 모든 요소를 ​​루트의 깊이와 함께 큐에 넣습니다. 모든 노드의 깊이를 최대 깊이와 비교하고 업데이트합니다.

암호알고리즘

  1. 함수 만들기 maxDepth () 위의 접근 방식에서 설명한 것과 유사
  2. If 뿌리 is 없는:
    • 0를 반환
  3. 초기화 최대 깊이 결과를 저장하기 위해
  4. 대기열 초기화 요소 트리 노드와 깊이를 포함하는
  5. 푸시 뿌리 대기열의 깊이는 1입니다.
  6. DaVinci에는 요소 비어 있지 않습니다 :
    • 프론트 노드와 높이를 다음과 같이 가져옵니다. 프론트노드프론트노드 깊이
    • 대기열에서 항목 꺼내기
    • If 프론트노드 깊이 is 보다 최대 깊이
      1. 업데이트 최대 깊이 = frontNodeDepth
    • If 프론트노드 is null 아님 :
      1. 모든 자식을 다음과 같은 깊이로 대기열에 넣습니다. 프론트노드 깊이 + 1
  7. 반환 최대 깊이
  8. 결과 인쇄

N-ary Tree Leetcode 솔루션의 최대 깊이 구현

C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

struct Node
{
    int value;
    vector <Node*> children;

    Node(int val)
    {
        value = val;
        children = {};
    }

    Node(int val , vector <Node*> childList)
    {
        value = val;
        children = childList;
    }
};

int maxDepth(Node* root)
{
    if(root == NULL)
        return 0;
    int maximumDepth = 0 , frontNodeDepth;

    queue <pair <Node* , int> > elements;
    elements.push({root , 1});
    Node* frontNode;
    while(!elements.empty())
    {
        frontNode = elements.front().first;
        frontNodeDepth = elements.front().second;
        elements.pop();
        if(frontNodeDepth > maximumDepth)
            maximumDepth = frontNodeDepth;

        if(frontNode != NULL)
        {
            for(Node* &child : frontNode->children)
                elements.push({child , frontNodeDepth + 1});
        }
    }

    return maximumDepth;
}

int main()
{
    Node* root = new Node(2);
    root->children = {new Node(3) , new Node(4) , new Node(5)};
    root->children[2]->children = {new Node(9)};
    cout << maxDepth(root) << '\n';
    return 0;
}

자바 프로그램

import java.lang.Math;
import java.util.*;

class Node
{
    int value;
    Node[] children;

    Node(int val)
    {
        value = val;
        children = new Node[]{};
    }

    Node(int val , Node[] childList)
    {
        value = val;
        children = childList;
    }
};

class Pair
{
    Node key;
    int value;
    Pair(Node root , int val)
    {
        key = root;
        value = val;
    }
}

class maximum_depth
{
    public static void main(String args[])
    {
        Node root = new Node(2);
        Node[] a = {new Node(3) , new Node(4) , new Node(5)};
        root.children = a;
        Node[] b = {new Node(9)};
        root.children[2].children = b;
        System.out.println(maxDepth(root));
    }

    static int maxDepth(Node root)
    {
        if(root == null)
            return 0;
        LinkedList <Pair> elements = new LinkedList <>();
        elements.add(new Pair(root , 1));
        Node frontNode;
        int maximumDepth = 0 , frontNodeDepth;

        while(elements.size() > 0)
        {
            frontNode = elements.peek().key;
            frontNodeDepth = elements.peek().value;
            elements.remove();
            if(frontNodeDepth > maximumDepth)
                maximumDepth = frontNodeDepth;

            if(frontNode != null)
            {
                for(int i = 0 ; i < frontNode.children.length ; i++)
                    elements.add(new Pair(frontNode.children[i] , frontNodeDepth + 1));
            }
        }
        return maximumDepth;
    }
}
3

N-ary Tree Leetcode 솔루션의 최대 깊이에 대한 복잡성 분석

시간 복잡성

의 위에) 다시 전체 나무를 횡단합니다. N = 나무의 크기

공간 복잡성

의 위에) 큐를 사용하여 깊이와 함께 트리의 모든 노드를 저장합니다.

코멘트를 남겨

Translate »
1