我有一个二叉树
2
/ \
3 4
/ \ \
5 1 8
/ \ / \
1 6 9 2
\
4
我想maximum possible triangular chord info sum
在给定的树中找到节点(在任意两个叶子和具有左右子节点的节点之间)。
三角弦将是
对于三角弦:
想象一下任意两片叶子之间的一条线,向上朝向根部,找到一个共同的父母(可以是父母、祖父母、祖父母,甚至是根本身)。向上移动时,对于每片叶子(对于任何叶子,我们要么只向上移动,要么只向左向左......等等,要么只向左向右......等等)意味着(左叶只会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);
}
我对我的方法有疑问。
任何人都可以提供另一种解决方案。??