N-Ary Tree LeetCode 솔루션의 지름

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

문제 설명 :

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

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

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

 

예 :

예제 1

핀

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

예제 2

핀

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

예제 3

핀

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(엔) 사용.