# 力扣练习——47 二叉树中的最大路径和()-其他

## 力扣练习——47 二叉树中的最大路径和()

1.问题描述

1

/ \

2   3

-10

/ \

9  20

/  \

15   7

#include <iostream>

#include <queue>

#include <cstdlib>

#include <cstring>

using namespace std;

struct TreeNode

{

int val;

TreeNode *left;

TreeNode *right;

TreeNode() : val(0), left(NULL), right(NULL) {}

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

};

TreeNode* inputTree()

{

int n,count=0;

char item[100];

cin>>n;

if (n==0)

return NULL;

cin>>item;

TreeNode* root = new TreeNode(atoi(item));

count++;

queue<TreeNode*> nodeQueue;

nodeQueue.push(root);

while (count<n)

{

TreeNode* node = nodeQueue.front();

nodeQueue.pop();

cin>>item;

count++;

if (strcmp(item,”null”)!=0)

{

int leftNumber = atoi(item);

node->left = new TreeNode(leftNumber);

nodeQueue.push(node->left);

}

if (count==n)

break;

cin>>item;

count++;

if (strcmp(item,”null”)!=0)

{

int rightNumber = atoi(item);

node->right = new TreeNode(rightNumber);

nodeQueue.push(node->right);

}

}

return root;

}

int main()

{

TreeNode* root;

root=inputTree();

int res=Solution().maxPathSum(root);

cout<<res<<endl;

}

2.输入说明

3.输出说明

4.范例

7-10 9 20 null null 15 7

42

5.代码

``````#include <iostream>

#include <queue>

#include <cstdlib>

#include <cstring>

using namespace std;

struct TreeNode

{

int val;

TreeNode *left;

TreeNode *right;

TreeNode() : val(0), left(NULL), right(NULL) {}

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

};

TreeNode* inputTree()

{

int n, count = 0;

char item[100];

cin >> n;

if (n == 0)

return NULL;

cin >> item;

TreeNode* root = new TreeNode(atoi(item));

count++;

queue<TreeNode*> nodeQueue;

nodeQueue.push(root);

while (count < n)

{

TreeNode* node = nodeQueue.front();

nodeQueue.pop();

cin >> item;

count++;

if (strcmp(item, "null") != 0)

{

int leftNumber = atoi(item);

node->left = new TreeNode(leftNumber);

nodeQueue.push(node->left);

}

if (count == n)

break;

cin >> item;

count++;

if (strcmp(item, "null") != 0)

{

int rightNumber = atoi(item);

node->right = new TreeNode(rightNumber);

nodeQueue.push(node->right);

}

}

return root;

}

int ans = INT_MIN;//初始值设置为最小
int dfs(TreeNode *root)
{
if (root == NULL)
return 0;
int left = dfs(root->left);//左子树提供的最大路径和
int right = dfs(root->right);//右子树提供的最大路径和
int interSum = root->val + left + right;//计算当前子树内部最大的路径和
ans = max(ans, interSum);
int outerSum = root->val + max(0, max(left, right));//计算当前子树向外提供的最大值
return max(outerSum,0);
}

int maxPathSum(TreeNode *root)
{
//递归解决问题

dfs(root);
return ans;
}

int main()

{

TreeNode* root;

root = inputTree();

int res = maxPathSum(root);

cout << res << endl;

}``````
————————

1.问题描述

1

/ \

2   3

-10

/ \

9  20

/  \

15   7

#include <iostream>

#include <queue>

#include <cstdlib>

#include <cstring>

using namespace std;

struct TreeNode

{

int val;

TreeNode *left;

TreeNode *right;

TreeNode() : val(0), left(NULL), right(NULL) {}

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

};

TreeNode* inputTree()

{

int n,count=0;

char item[100];

cin>>n;

if (n==0)

return NULL;

cin>>item;

TreeNode* root = new TreeNode(atoi(item));

count++;

queue<TreeNode*> nodeQueue;

nodeQueue.push(root);

while (count<n)

{

TreeNode* node = nodeQueue.front();

nodeQueue.pop();

cin>>item;

count++;

if (strcmp(item,”null”)!=0)

{

int leftNumber = atoi(item);

node->left = new TreeNode(leftNumber);

nodeQueue.push(node->left);

}

if (count==n)

break;

cin>>item;

count++;

if (strcmp(item,”null”)!=0)

{

int rightNumber = atoi(item);

node->right = new TreeNode(rightNumber);

nodeQueue.push(node->right);

}

}

return root;

}

int main()

{

TreeNode* root;

root=inputTree();

int res=Solution().maxPathSum(root);

cout<<res<<endl;

}

2.输入说明

3.输出说明

4.范例

7-10 9 20 null null 15 7

42

5.代码

``````#include <iostream>

#include <queue>

#include <cstdlib>

#include <cstring>

using namespace std;

struct TreeNode

{

int val;

TreeNode *left;

TreeNode *right;

TreeNode() : val(0), left(NULL), right(NULL) {}

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

};

TreeNode* inputTree()

{

int n, count = 0;

char item[100];

cin >> n;

if (n == 0)

return NULL;

cin >> item;

TreeNode* root = new TreeNode(atoi(item));

count++;

queue<TreeNode*> nodeQueue;

nodeQueue.push(root);

while (count < n)

{

TreeNode* node = nodeQueue.front();

nodeQueue.pop();

cin >> item;

count++;

if (strcmp(item, "null") != 0)

{

int leftNumber = atoi(item);

node->left = new TreeNode(leftNumber);

nodeQueue.push(node->left);

}

if (count == n)

break;

cin >> item;

count++;

if (strcmp(item, "null") != 0)

{

int rightNumber = atoi(item);

node->right = new TreeNode(rightNumber);

nodeQueue.push(node->right);

}

}

return root;

}

int ans = INT_MIN;//初始值设置为最小
int dfs(TreeNode *root)
{
if (root == NULL)
return 0;
int left = dfs(root->left);//左子树提供的最大路径和
int right = dfs(root->right);//右子树提供的最大路径和
int interSum = root->val + left + right;//计算当前子树内部最大的路径和
ans = max(ans, interSum);
int outerSum = root->val + max(0, max(left, right));//计算当前子树向外提供的最大值
return max(outerSum,0);
}

int maxPathSum(TreeNode *root)
{
//递归解决问题

dfs(root);
return ans;
}

int main()

{

TreeNode* root;

root = inputTree();

int res = maxPathSum(root);

cout << res << endl;

}``````