6

私は二分木を持っています

         2
       /   \
      3     4
     / \     \
    5   1     8
   / \       / \
  1   6     9   2
                 \
                  4

maximum possible triangular chord info sum指定されたツリー内のノード (任意の 2 つの葉と左右の両方の子を持つノードの間)を見つけたいです。

三角形のコードは

三角弦の場合:

任意の 2 つの葉の間の線を想像して、根に向かって上に進み、共通の親 (親、祖父母、祖父母、または根自体でさえあります) を見つけます。上に移動している間、各葉について (どの葉についても、左、左、左だけを上に移動する必要があるか、または、右、右、右のみ、など) を意味します (左の葉はright上のみ、右のみを移動します)。葉はleft上向きにのみ移動します....だから、任意の単一の葉の場合、we can not move in both direction while moving upwards..今、三角形の形を取得しますa side may contain any no. of nodes/links possible.. triangular shape does not contain any extra internal branchesその三角形の形が三角弦になります。

覚えておいてくださいevery leaf node is also always a triangular chord（二分木に三角形の弦がない場合にデフォルトのケースを作成するだけです）

今

    maximum triangular chord will be that triangular chord 
which have maximum total in sum of all its node info.

私たちはする必要がありますreturn that maximum total.

    If we do not have triangular shaped chord.. 
then we have to return the leaf with maximum info.

例えば

   8                    
  / \
 2   3
      \
       3

三角弦です

  8                     
  / \                   
 2   3
  \   \
   4   1

単一ノード 4 を持つサブツリーのみが最大三角弦になります (その合計は単一ノード 1 を持つ別の三角弦よりも大きいため) ツリー全体が三角弦になるわけではありません

    8                    
   / \
  2   3
 /     \
4       3

三角弦です

したがって、問題の最初の行の最初のツリーの解は

8+9+2+4 = 23

私はこの問題にひどく閉じ込められています。

私は大まかなアプローチをしています

サブツリーのルートとして leftchild を再帰的に呼び出し、サブツリーのルートとして rightchild と同じ左の最大三角和音を見つけます。

leftmax と rightmax の最大値を追加し、rood ノードに追加して戻ります

C ++のmycodeは次のとおりです。

int maxtri(node* n) 
{
  if(n) 
  {
    lsum = maxtri(n->left);
    rsum = maxtri(n->right);
    k = maxof(lsum,rsum);
    return (n->info + k);
  }
}

編集：私の別の再帰的アプローチ

int l =0, r =0;
int maxtri(node* n)
{
 if (n == NULL) return 0;
 if (!(n->left) && !(n->right)) return n->info;
 if ((n->left) && (n->right))
 {
  l = maxtri(n->left);
  r = maxtri(n->right);
 }
 if ((n->left) && !(n->right)) 
 {  
  l = l + maxtri(n->left);
 }
 if (!(n->left) && (n->right)) 
 {
  r = r + maxtri(n->right);
 }
 return (l+r+n->info);
}

私は自分のアプローチに疑問を持っています。

誰かが別の解決策を与えることができますか??

4

2 に答える 2

1

このロジックはどうですか:
各ノードについて、左部分と右部分をトラバースします。分岐が見つかった場合は、計算でこのノードを考慮しないでください。そうでない場合は、これを考慮してください。さらに、計算ノードの部分は、左右のノードを持つか、葉ノードにする必要があります。

注: 適切にテストしていませんが、動作するはずです。

// Node by Node traverse the tree  

void addSum(Node *head, vector<int>& sum)
{
if (head == NULL)
    return;
else {
    int s = traverseThisNode(head);
    sum.push_back(s); // Add to vector
    addSum(head->left, sum);
    addSum(head->right, sum);
}
}

// For each node traverse left & right  

int traverseThisNode(Node *head)
{
if (head && head->left && head->right) {
    Node *temp = head;  // To traverse right portion of this node
    int sum = head->value;
    while(head->left) {   // Traverse right
        head = head->left;
        sum = sum + head->value;
        if (head->right) {  // Condition to check if there is any branching
            sum = 0;
            break;
        }
    }
    while(temp->right && sum != 0) {  // Traverse Right now
        temp = temp->right;
        sum = sum + temp->value;
        if (temp->left) { // Condition to check if there is any branching
            sum = 0;
            break;
        }
    }

    return sum;
} else if (head && !head->left && !head->right) {
    return head->value;   // To add leaf node
}
return 0;
}

Now you have vector containing all the value of triangular in the tree, traverse it and   
find the maximum.
int maximum() 
{
  // Traverse the vector "sum" & find the maximum
}
于 2013-05-08T13:34:23.507 に答える
0

質問を理解している限り、アプローチの疑似コードを書きます。

Max = min_value; //possibly 0 if no negative value is allowed for nodes.
sum = 0;
for each node in the tree
    temp = node;
    sum+= temp->data  //collects data at the current level, the current level may be leaf too.
    Until temp->left is not null, // Traversing uni-directionally to the left most deep and collecting data.
       temp = temp->left
       sum+=temp->data 
    Until temp->right is not null,  // Traversing uni-directionally to the right most deep and collecting data.
       temp = temp->right
       sum+= temp->data 

    if(sum > Max)
      Max = sum;

    sum = 0;  



print Max;
于 2013-05-07T17:50:03.737 に答える