路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。
使用前序来创建树
tnode* createtree(){ char data; tnode *T=nullptr; cin >> data; if ('#'==data) { T=nullptr; } else{ T=new tnode; T->data=data; T->lt=createtree(); T->rt=createtree(); } return T; }//类似这种来创建二叉树
以上为解题思路。
然后就是算法的实现
int maxgain(tnode* root,int&val){ if (root==nullptr) { return 0; } int left=maxgain(root->lt, val); int right=maxgain(root->rt, val); int ret=root->data+max(0,left)+max(0,right);//这为后两种情况下的权值,同时需要考虑权值的为负数的情况, val的初始值应设置为INT_MIN int lmr=root->data+max(0,max(left, right));//这为第一种情况 val=max(val, ret, lmr); return ret;//递归 }
然后主函数调用maxgain即可实现