N-Ary Tree LeetCode 솔루션의 지름

난이도 중급
자주 묻는 질문 Facebook 구글 Microsoft
깊이 우선 검색 나무조회수 54

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 설명 :

또한 N-Ary Tree LeetCode 솔루션의 지름 – 주어진 뿌리 의 N 항 트리, 나무의 지름 길이를 계산해야 합니다.

N-ary 트리의 지름은 가장 긴 트리의 두 노드 사이의 경로. 이 경로는 루트를 통과할 수도 있고 통과하지 않을 수도 있습니다.

(Nary-Tree 입력 직렬화는 레벨 순서 순회로 표현되며, 각 자식 그룹은 null 값으로 구분됩니다.)

 

예 :

예제 1

N-Ary Tree LeetCode 솔루션의 지름

Input: root = [1,null,3,2,4,null,5,6]
Output: 3
Explanation: Diameter is shown in red color.

예제 2

N-Ary Tree LeetCode 솔루션의 지름

Input: root = [1,null,2,null,3,4,null,5,null,6]
Output: 4

예제 3

N-Ary Tree LeetCode 솔루션의 지름

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: 7

직관:

  • 우리는 계산하도록 요청받습니다. N항 트리의 지름, 다음과 같이 정의됩니다. 최장 경로 트리의 두 노드 사이.
  • n개의 자식이 있는 노드를 고려하면 다음이 있습니다. nC2 or n 2개의 경로 선택 이 노드를 통과합니다.
  • 가장 긴 경로는 최대 높이1 + 최대 높이2 +2 여기서 maxheight1 및 maxheight2는 두 개의 최대 높이 N 자녀 사이.
  • 가장 긴 경로의 길이 노드 통과 = N명의 자식 중 첫 번째 최대 키 + N명의 자식 중 두 번째 최대 키 + 1
  • 위의 직관으로 나무의 지름을 찾으려면 모든 노드를 반복하고 최대 높이의 두 자식을 선택해야 합니다.
  • 모든 노드를 반복하려면 다음을 사용할 수 있습니다.  깊이 우선 검색.

알고리즘 :

  • 초기화 전역 변수 지름, 그리고 각 노드 업데이트 변수에 대해 계산 가장 긴 경로의 길이 노드를 통과합니다.
  • 함수 정의 높이(노드 루트) {} 그것은 반환합니다 최대 높이.
  • 높이 함수에서 모든 자식을 반복하고 가장 좋은 두 자식 키를 선택합니다. 최대 높이1최대 높이2.
  • 이제 직경 전역 변수 이 노드를 통과하는 가장 긴 경로를 사용합니다.
  •  마지막으로 높이 함수에서 maxheight1을 반환합니다.
  • 높이 함수 실행 후 반환 직경 전역 변수, 주요 기능에서 직경(노드 루트){}.

암호

N-Ary Tree Leetcode Java 솔루션의 지름:

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    
    public Node() {
        children = new ArrayList<Node>();
    }
    
    public Node(int _val) {
        val = _val;
        children = new ArrayList<Node>();
    }
    
    public Node(int _val,ArrayList<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    protected int diameter=0;
    public int diameter(Node root) {
        height(root);
       return this.diameter;
    }
    // Return  the maxheight in N-arry tree
    public int height(Node root){
         int maxheight1=0;
        int maxheight2=0;
        for(Node child:root.children){
            int height=height(child)+1;
            if(height>maxheight1){
                maxheight2=maxheight1;
                maxheight1=height;
            }
            else if(height>maxheight2){
                maxheight2=height;
            }
        }
        this.diameter=Math.max(maxheight1+maxheight2,this.diameter);
        return maxheight1;
    }
    
}

N-Ary Tree Leetcode C++ 솔루션의 지름:

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
     int maxDiameter=0;
public:
    int diameter(Node* root) {
         height(root);
       return this->maxDiameter;
    }
    int height(Node* root){
         int maxheight1=0;
        int maxheight2=0;
        for(auto child:root->children){
            int rootHeight=height(child)+1;
            if(rootHeight>maxheight1){
                maxheight2=maxheight1;
                maxheight1=rootHeight;
            }
            else if(rootHeight>maxheight2){
                maxheight2=rootHeight;
            }
        }
        this->maxDiameter=max(maxheight1+maxheight2,this->maxDiameter);
        return maxheight1;
    }
};

N-Ary 트리의 지름에 대한 복잡성 분석:

시간 복잡성

O(N), 트리의 각 노드를 반복하기 때문에 한 번만 를 통해 재귀.

.공간 복잡성 

O(N), 재귀 스택으로 0(엔) 사용.

균열 시스템 설계 인터뷰
Translate »