查找n-ary樹的根到葉的最大路徑，不包括總和中兩個相鄰節點的值

Question

我最近接受了採訪，並被問及以下問題。

給定一個n元樹，找到從根到葉的最大路徑，使得最大路徑不包含來自任何兩個相鄰節點的值。

（另一個編輯：這兩個節點只能爲正值。）

（從評論編輯：相鄰節點是指共享一個直接的邊緣節點，因爲它的一棵樹，這意味着親子所以如果。我包括父，我不能包括兒童和反之亦然）

，例如：

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

在上述例子中，不相鄰的兩個最大路徑將是14沿着路徑5-> 10 > 9。我在最後的總和中包括5和9，但不包括10，因爲它會違反兩個相鄰的節點條件。

我建議以下算法。雖然我對此相當確信，但我的面試官對此似乎並沒有信心。因此，我想仔細檢查我的算法是否正確。它似乎適用於我能想到的各種測試案例：對於每個節點X，令F（X）爲從最大和中沒有兩個相鄰值的根到X的最大總和。 （X）= Max（F（parent（X）），val（X）+ F（grandParent（X）））的計算公式。

的解決辦法是 解決方案= MAX（F（葉節點））

這是大概我想出了代碼：

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; 
    } 
} 

編輯：忘了提，我的主要目的問這個問題是要知道我的算法是否正確，而不是問一個新的算法。

編輯：我有理由相信我的算法也應該有效。

我在網上淘了類似的問題和碰到這個問題就來了： https://leetcode.com/problems/house-robber/?tab=Description

這是非常相似的問題，所不同的是，現在是一個數組，而不是樹。

在這種情況下，形式F（X）= Max（F（X-1），a [x] + F（X-2））起作用。

這是我接受代碼：

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

自然解決辦法是計算每個節點X的兩個值：最大路徑從X到葉包括X和最大路徑從X到葉，不含X，我們稱它們爲MaxPath（X）和MaxExcluded（X）。

對於葉L最大路徑（L）是值（L）和最大被覆蓋（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; 
    } 
}