带权值二叉树的路径最长值与路径
发布时间
阅读量：
阅读量
一、Problem
Given a binary tree, every node has a weight, then you need to find out the path that can make the total weight of all nodes it go through is the maximum and show the path. The weight is always positive.
二、Solution
方法一、 (该方法只能找到路径最大值并不能表示最大值的路径）
int getPath(TreeNode* root, int now) {
if (root != NULL) {
int lnow = getPath(root->lchild, root->data);
int rnow = getPath(root->rchild, root->data);
int nows = lnow > rnow ? lnow : rnow;
return now + nows;
} else {
return now;
}
}
int findMaxPath(TreeNode *root) {
if (root != NULL) {
int lnow = getPath(root->lchild, root->data);
int rnow = getPath(root->rchild, root->data);
int now = lnow > rnow ? lnow : rnow;
return now;
} else {
return 0;
}
}方法二、（该方法可以找到最大值且可以输出节点数据，不过得设置一个全局变量sum）
int sum = 0; int height(TreeNode *t) { //递归求树高
int hl,hr;
if(t == NULL) {
return 0;
}
hl = height(t->lchild)+1; //最下面的左孩子加一
hr = height(t->rchild)+1; //最下面的右孩子加一
return (hl > hr?hl:hr); //比较谁大就取谁
}
void longest_path(TreeNode *root) { //递归求最长路径
if (t!= NULL) {
cout << root->data << " "; // 输出节点数据
sum += root->data;// 计算路径最大值
if (height(root->lchild) > height(root->rchild)) {
longest_path(root->lchild);
} else {
longest_path(root->rchild);
}
}
}上述两种方法各取所需喽！如有更好的方法欢迎欢迎
全部评论 (0)
还没有任何评论哟~