c++ - 求出最大可能三角弦的和

我有一棵二叉树

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

我想在给定的树中找到节点的maximum possible triangular chord info sum(在任意两个叶子之间以及一个具有左右两个子节点的节点之间)。

三角弦将是

对于三角和弦:

想象一下任何两片叶子之间的一条线，向上朝根，找到一个共同的 parent (可以是 parent ，祖 parent ，祖 parent 或什至是根自己)。在向上移动时，对于每片叶子(对于任何叶子，我们都必须只向左左左向上移动..等等，或者只向右，右，右，右等等。)意味着(左叶子只能将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);
}

我对我的做法有疑问。

任何人都可以提供其他解决方案。

最佳答案

那么这个逻辑呢:
对于遍历左侧和右侧的每个节点，如果找到任何分支，则在计算中不要考虑该节点，否则请考虑这一点。此外，对于计算节点而言，该节点应该具有左右节点，或者应该是叶节点。

注意:我没有对其进行正确的测试，但是我认为它应该可以工作。

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

关于c++ - 求出最大可能三角弦的和，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16397354/