이 문제에서 우리는 N 항 트리즉, 노드가 2 개 이상의 자식을 가질 수 있도록하는 트리입니다. 나무 뿌리에서 가장 먼 잎의 깊이를 찾아야합니다. 이를 최대 수심이라고합니다. 경로의 깊이는 경로의 노드 수입니다.
차례
예
2
/ | \
3 4 6
\
9
3
설명: 값이 9 인 잎은 뿌리에서 가장 멀고 깊이는 3. 그래서 우리는 3을 인쇄합니다.
2
/ \
3 6
/ | \
4 7 9
3
설명: 값이 4,7 및 9 인 잎은 뿌리에서 가장 멀고 깊이는 3. 그래서 우리는 3을 인쇄합니다.
접근하다(재귀)
이진 트리의 최대 깊이는 노드의 왼쪽 및 오른쪽 자식에서 재귀 함수를 호출하여 계산됩니다. 마찬가지로 N 항 트리의 경우 모든 노드의 모든 자식에 대해 재귀 함수를 호출하여 최대 깊이를 계산할 수 있습니다. 이 접근 방식은 재귀 적이며 트리의 단일 패스 만 필요합니다.
암호알고리즘
- 함수 만들기 maxDepth () 트리의 최대 깊이를 반환합니다. 뿌리 그것에 전달됩니다
- If 뿌리 null 인 경우 :
- 0를 반환
- 변수 초기화 최대 깊이 N 항 트리의 최대 깊이 저장
- 매회마다 아이 현재 루트의 자식 목록에서 :
- 세트 maximumDepth = max (maxDepth (root.left), maxDepth (root.right))
- 반환 최대 깊이 + 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 항 트리의 크기.
공간 복잡성
의 위에) 재귀 호출을 위해 메모리에 스택 프레임을 저장하기 때문입니다.
접근하다(반복적 인)
스택 또는 큐를 사용하여 루트에서 노드와 해당 깊이를 저장하여 위의 프로세스를 반복적으로 수행 할 수 있습니다. 최대 깊이는이 과정에서 얻은 모든 뿌리의 최대 깊이입니다. 이를 위해 큐를 사용하고 트리의 모든 요소를 루트의 깊이와 함께 큐에 넣습니다. 모든 노드의 깊이를 최대 깊이와 비교하고 업데이트합니다.
암호알고리즘
- 함수 만들기 maxDepth () 위의 접근 방식에서 설명한 것과 유사
- If 뿌리 is 없는:
- 0를 반환
- 초기화 최대 깊이 결과를 저장하기 위해
- 대기열 초기화 요소 트리 노드와 깊이를 포함하는
- 푸시 뿌리 대기열의 깊이는 1입니다.
- DaVinci에는 요소 비어 있지 않습니다 :
- 프론트 노드와 높이를 다음과 같이 가져옵니다. 프론트노드 및 프론트노드 깊이
- 대기열에서 항목 꺼내기
- If 프론트노드 깊이 is 큰 보다 최대 깊이
- 업데이트 최대 깊이 = frontNodeDepth
- If 프론트노드 is null 아님 :
- 모든 자식을 다음과 같은 깊이로 대기열에 넣습니다. 프론트노드 깊이 + 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 , 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 = 나무의 크기
공간 복잡성
의 위에) 큐를 사용하여 깊이와 함께 트리의 모든 노드를 저장합니다.
