C++刷leetcode(124. 二叉树中的最大路径和)【递归】
本帖最后由 糖逗 于 2020-5-8 17:37 编辑题目描述：
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1:
输入:
1
/ \
2 3
输出: 6
示例 2:
输入: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
输出: 42
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
#include<iostream>
#include <malloc.h>
#include <vector>
#include <math.h>
#include <queue>
#include<vector>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x): val(x), left(NULL), right(NULL){
}
};
TreeNode* CreateTree(vector<int> input){
TreeNode* res = (TreeNode*)malloc(sizeof(TreeNode)*input.size());
for(int i = 0; i < input.size(); i++){
res.val = input;
res.left = NULL;
res.right = NULL;
}
for(int i= 0; i < input.size(); i++){
if(2*i+1 < input.size()){
res.left = &res;
}
if(2*i+2 < input.size()){
res.right = &res;
}
}
return res;
}
void middle(TreeNode* root, vector<vector<int> >& res, int left, int right, int depth){
if(root == NULL) return;
int insert = left + (right - left) / 2;
res = root->val;
middle(root->left, res, left, insert - 1, depth + 1);
middle(root->right, res, insert + 1, right, depth + 1);
}
int treeDepth(TreeNode* root){
if(root == NULL || root -> val == 0) return 0;
return max(treeDepth(root->left) + 1, treeDepth(root->right) + 1);
}
void PrintTree(TreeNode* root) {
int depth = treeDepth(root);
int width = pow(2, depth) - 1;
vector<vector<int> > res(depth, vector<int>(width, 0));
middle(root, res, 0, width - 1, 0);
for(int i = 0; i < res.size(); i++){
for(int j = 0; j < res.size();j++){
if(res == 0){
cout<< " ";
}
else{
cout << res;
}
}
cout << endl;
}
cout << "------------------" << endl;
}
int dfs(TreeNode* root, int& res){
if(root == NULL) return 0;
int left = max(dfs(root -> left, res), 0);
int right = max(dfs(root -> right, res), 0);
int temp = root -> val + right + left;
res = max(res, temp);
return root -> val + max(left, right);
}
int solution(TreeNode* root){
int res = INT_MIN;
dfs(root, res);
return res;
}
int main(void){
vector<int> input1;
cout << "send numbers for thetree" << endl;
int number1;
while(cin >> number1){
input1.push_back(number1);
}
cin.clear();
TreeNode* root = CreateTree(input1);
PrintTree(root);
int res = solution(root);
cout << res << endl;
return 0;
}
注意事项：
1.参考链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/er-cha-shu-zhong-de-zui-da-lu-jing-he-by-ikaruga/ class Solution {
public:
int comput(TreeNode*root, int &res){
if(root == NULL)return 0;
int left = comput(root -> left, res);
int right = comput(root -> right, res);
int both = root -> val + max(left, 0) + max(right, 0);//双侧情况
res = max(res, both);
return root->val + max(max(left, 0), max(right, 0));//单侧情况
}
int maxPathSum(TreeNode* root) {
if(root == NULL)return 0;
int res = INT_MIN;//存在负数的情况
comput(root, res);
return res;
}
};
页:
[1]