두 개의 인접 노드 값을 포함하지 않고 n 트리 트리의 루트에서 리프까지의 최대 경로를 찾습니다.

Question

최근 인터뷰를 통해 다음 질문을 받았습니다.

n-ary 트리가 주어지면 최대 경로에 인접한 두 노드의 값이 포함되지 않도록 루트에서 리프까지의 최대 경로를 찾습니다.

(또 다른 편집 : 노드는 양의 값을 가질 것이다.)

(코멘트에서 편집 :. 인접 노드는 직접 가장자리를 공유 노드가 있기 때문에 나무, 그것은 부모 - 자식을 의미 의미 그래서 만약. I 부모를 포함 I 반대로 아이를 포함 할 수 없음), 예를 들어

:.

위의 예에서

 5 
    /  \ 
    8   10 
/\  / \ 
1 3  7 9 

인접한 두없이 최대 경로가 경로 5-> 10- 함께 14 것 > 9. 최종 합계에는 5와 9를 포함 시키지만 인접 노드 조건을 위반하지 않으므로 10을 포함하지 않습니다.

다음 알고리즘을 제안했습니다. 나는 그것에 대해 꽤 확신했지만, 내 인터뷰 담당자는 그것에 대해 확신하지 못했습니다. 따라서 알고리즘이 맞는지 아닌지 다시 한 번 확인하고 싶습니다.

각 노드 X에 대해 최대 합계에서 두 인접 값이없는 루트에서 X까지의 최대 합계를 F (X)로합시다.

F (X) = Max (F (parent (X)), val (X) + F (grandParent (X)) 계산식은 다음과 같습니다.

class Node 
{ 
    int coins; 
    List<Node> edges; 

    public Node(int coins, List<Node> edges) 
    { 
     this.coins = coins; 
     this.edges = edges; 
    } 
} 

class Tree 
{ 
    int maxPath = Integer.MIN_VALUE; 

    private boolean isLeafNode(Node node) 
    { 
    int size = node.edges.size(); 
    for(int i = 0; i < size; i++) 
    { 
     if(node.edges.get(i) != null) 
     return false; 
    } 
    return true; 
    } 

    // previous[0] = max value obtained from parent 
// previous[1] = max value obtained from grandparent 
    private void helper(Node node, int[] previous) 
    { 
    int max = Math.max(previous[0], max.val + previous[1]); 
    //leaf node 

    if(isLeafNode(node)) 
    { 
     maxPath = Math.max(maxPath, max); 
     return; 
    } 

    int[] temp= new int[2]; 
    temp[0] = max; 
    temp[1] = prev[0]; 
    for(int i = 0; i < node.edges.size(); i++) 
    { 
     if(node.edges.get(i) != null) 
     { 
     helper(node.edges.get(i), temp); 
     } 
    } 
    } 


    public int findMax(Node node) 
    { 
    int[] prev = new int[2]; 
    prev[0] = 0; 
    prev[1] = 0; 
    if(node == null) return 0; 
    helper(node, prev); 
    return maxPath; 
    } 
} 

편집 :

솔루션 솔루션 = 최대 (F (잎 노드))

이 내가 생각 해낸 대략 코드였다했을 언급하는 것을 잊었다 나의 주된 목적에서 이 질문을하는 것은 내 알고리즘이 새로운 알고리즘을 요구하는 것이 아니라 올바른 것인지를 아는 것입니다.

편집 : 알고리즘이 작동해야한다고 생각하는 이유가 있습니다.

나는 비슷한 질문 인터넷을 수색하고이 질문에 건너 온되었다 https://leetcode.com/problems/house-robber/?tab=Description

그것은 지금 대신 나무의 배열입니다 것을 제외하고 위의 문제에 매우 유사하다.

이 경우 공식 F (X) = Max (F (X-1), a [x] + F (X-2))가 작동합니다. 잎에 X에서 X 및 최대 경로, X를 제외한 포함 X에서 잎에 최대 경로 : 자연 솔루션은 각 노드 X이 개 값을 계산하는 것입니다

public class Solution { 
    public int rob(int[] nums) { 

     int[] dp = new int[nums.length]; 
     if(nums.length < 1) return 0; 
     dp[0] = nums[0]; 
     if(nums.length < 2) return nums[0]; 
     dp[1] = Math.max(nums[0], nums[1]); 

     for(int i = 2; i < nums.length; i++) 
     { 
      dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]); 
     } 
     return dp[nums.length-1]; 

    } 
} 

Answer 1

:

여기 내 승인 코드 MaxPath (X)와 MaxExcluded (X)라고 부르 자.

잎 L MaxPath (L)는 값 (L)이고 MaxExcluded (L)은 0입니다.내부 노드 X에 대한

:

MaxPath(X) = Value(X) + Max over child Y of: MaxExcluded(Y) 
MaxExcluded(X) = Max over child Y of : Max(MaxExcluded(Y), MaxPath(Y)) 

첫 번째 줄은 당신이 X를 포함하는 경우, 당신은 아이를 제외 할 필요가 있다는 것을 의미한다. 두 번째는 X를 제외하면 자녀를 포함하거나 제외시킬 수 있다는 것입니다.

O (트리의 크기)에서 잎과 부모로가는 계산이 가능한 노드에 대한 간단한 재귀 함수입니다.

편집 : 재귀 관계도 위에서 아래로 작동하며이 경우 MaxExcluded(Y)이 실제로 MaxPath(Parent(Y))이라는 관찰에 따라 두 값을 저장하지 않아도됩니다. 그러면이 질문에 주어진 해결책을 얻을 수 있습니다.

Answer 2

구현 @ RafałDowgird가 설명했습니다.

/*       5 
*    8     10 
*   1  3   7   9 
*  4 5 6 11 13  14 3  4 
* 
* 
*/ 




public class app1 { 

public static void main(String[] args) { 
    Node root = new Node(5); 
    root.left = new Node(8);root.right = new Node(10); 
    root.left.left = new Node(1);root.left.right = new Node(3); 
    root.right.left = new Node(7);root.right.right = new Node(9); 
    root.left.left.left = new Node(4);root.left.left.right = new Node(5); 
    root.left.right.left = new Node(6);root.left.right.right = new Node(11); 
    root.right.left.left = new Node(13);root.right.left.right = new Node(14); 
    root.right.right.right = new Node(4); 
    System.out.println(findMaxPath(root)); 

} 

private static int findMaxPath(Node root) { 


    if (root == null) return 0; 

    int maxInclude = root.data + findMaxPathExcluded(root); 
    int maxExcludeLeft = Math.max(findMaxPath(root.left), findMaxPathExcluded(root.left)); 
    int maxExcludeRight = Math.max(findMaxPath(root.right), findMaxPathExcluded(root.right)); 
    return Math.max(maxInclude, Math.max(maxExcludeLeft, maxExcludeRight)); 
} 

private static int findMaxPathExcluded(Node root) { 

    if(root == null) return 0; 
    int left1 = root.left!=null ? findMaxPath(root.left.left) : 0; 
    int right1 = root.left!=null ? findMaxPath(root.left.right) : 0; 
    int left2 = root.right!=null ? findMaxPath(root.right.left) : 0; 
    int right2 = root.right!=null ? findMaxPath(root.right.right) : 0; 

    return Math.max(left1, Math.max(right1, Math.max(left2, right2))); 
} 

} 
class Node{ 
    int data; 
    Node left; 
    Node right; 
    Node(int data){ 
    this.data=data; 
    } 
}