合計で2つの隣接ノードの値を含まずにルートからリーフまでのn-aryツリーの最大パスを見つける

Question

最近インタビューを受け、次の質問がありました。

n-aryツリーが与えられた場合、最大パスに隣接する2つのノードからの値が含まれないように、ルートからリーフまでの最大パスを見つけます。

（別の編集：ノードは正の値のみを持っているでしょう。）。

（コメント編集：。その木は、それが親子を意味するのでそうであれば、隣接ノードが直接のエッジを共有するノードを意味し、私は子供およびその逆を含むことができない、親を含む）

例えば：

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

上記の例では、隣り合うことなく、最大パスが>経路5に沿って14あろう10- > 9。最終的な合計には5と9が含まれていますが、隣接ノードの2つの条件に違反するため、10には含まれません。

次のアルゴリズムを提案しました。私はそれについてかなり確信していましたが、面接官はそれについて自信を持っていませんでした。したがって、私のアルゴリズムが正しいかどうかを再確認したい。

各ノードXについて、最大総和の2つの隣接する値がない場合のルートから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とmaxパス、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を含んでいる場合、あなたはその子を除外しなければならないことを意味します。 2つ目は、Xを除外すると、子どもを含めたり除外したりすることができるということです。

これは、ノード上の単純な再帰関数です。これは、O（ツリーのサイズ）で葉と親になると計算できます。

編集：再帰的リレーションもトップダウンで動作します。この場合、実際にMaxExcluded(Y)ということが2つの値を保存する必要はありません。これは実際には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; 
    } 
}