c++ - 找到最大可能三角弦的总和

Question

我有一个二叉树

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

我想找到给定树中节点(在任意两个叶子和具有左右子节点的节点之间)的最大可能三角弦信息和。

一个三角和弦将是

三角弦:

想象一下任意两片叶子之间的一条线，向上走向根，找到一个共同的 parent (可以是 parent 、祖 parent 、祖 parent ，甚至是根本身)。向上移动时，对于每片叶子(对于任何叶子，我们要么只能向上移动左左......等等，要么只能右右右右......等等)意味着(左叶只会向右移动 仅向上，右叶将向左 仅向上移动.....因此对于任何单片叶子，我们不能在向上移动时同时向两个方向移动) .. 现在我们得到一个三角形.. 其中 边可以包含任何 no。可能的节点/链接数.. 现在，如果那个三角形不包含任何额外的内部分支。那个三角形将是一个三角形弦。

请记住，每个叶节点也始终是一个三角形弦(如果二叉树没有任何三角形弦，这只是创建默认情况)

现在

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

我们需要返回最大总数。

    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 作为子树的根并找到左边的最大三角弦和然后右子作为子树的根。

将leftmax和rightmax的最大值相加，并添加到rood节点并返回

在 C++ 中我的代码是:

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

我怀疑我的方法。

谁能给出另一个解决方案？？

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