[LeetCode]*124.Binary Tree Maximum Path Sum

本文主要是介绍[LeetCode]*124.Binary Tree Maximum Path Sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目】

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1/ \2   3

Return 6.

【分析】

需要考虑以上两种情况：

1 左子树或者右子树中存有最大路径和不能和根节点形成一个路径

2 左子树右子树和根节点形成最大路径

【代码】

/*********************************
*   日期：2014-12-23
*   作者：SJF0115
*   题号: Binary Tree Maximum Path Sum
*   来源：https://oj.leetcode.com/problems/binary-tree-maximum-path-sum/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};class Solution {
public:int maxPathSum(TreeNode *root) {if(root == NULL){return 0;}//ifmaxSum = INT_MIN;maxPath(root);return maxSum;}
private:int maxSum;int maxPath(TreeNode *node){if(node == NULL){return 0;}//if// 左子树最大路径值(路径特点：左右节点只能选一个)int leftMax = maxPath(node->left);// 右子树最大路径值(路径特点：左右节点只能选一个)int rightMax = maxPath(node->right);// 以node节点的双侧路径((node节点以及左右子树))int curMax = node->val;if(leftMax > 0){curMax += leftMax;}//ifif(rightMax > 0){curMax += rightMax;}//ifmaxSum = max(curMax,maxSum);// 以node节点的单侧路径(node节点以及左右子树的一个)if(max(leftMax,rightMax) > 0){return max(leftMax,rightMax) + node->val;}else{return node->val;}}
};//按先序序列创建二叉树
int CreateBTree(TreeNode*& T){int data;//按先序次序输入二叉树中结点的值,-1表示空树cin>>data;if(data == -1){T = NULL;}else{T = (TreeNode*)malloc(sizeof(TreeNode));//生成根结点T->val = data;//构造左子树CreateBTree(T->left);//构造右子树CreateBTree(T->right);}return 0;
}int main() {Solution solution;TreeNode* root(0);CreateBTree(root);cout<<solution.maxPathSum(root);
}

【温故】

/*---------------------------------------
*   日期：2015-04-30
*   作者：SJF0115
*   题目: 124.Binary Tree Maximum Path Sum
*   网址：https://leetcode.com/problems/binary-tree-maximum-path-sum/
*   结果：AC
*   来源：LeetCode
*   博客：
-----------------------------------------*/
#include <iostream>
#include <vector>
using namespace std;struct TreeNode{int val;TreeNode *left;TreeNode *right;TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};class Solution {
public:int maxPathSum(TreeNode *root) {if(root == NULL){return 0;}//ifint maxSum = INT_MIN;maxPath(root,maxSum);return maxSum;}
private:int maxPath(TreeNode *root,int &maxSum){if(root == NULL){return 0;}//if// 后序遍历// root左子树最大路径值int leftMax = maxPath(root->left,maxSum);// root右子树最大路径值int rightMax = maxPath(root->right,maxSum);// 双侧最大路径值int curMax = root->val;if(leftMax > 0){curMax += leftMax;}//ifif(rightMax > 0){curMax += rightMax;}//ifmaxSum = max(maxSum,curMax);// 如果是某节点的子树时只能返回单侧最大路径值int oneSideMax = max(leftMax,rightMax);if(oneSideMax > 0){return root->val + oneSideMax;}//ifelse{return root->val;}}
};//按先序序列创建二叉树
int CreateBTree(TreeNode*& T){int data;//按先序次序输入二叉树中结点的值,-1表示空树cin>>data;if(data == -1){T = NULL;}else{T = new TreeNode(data);//构造左子树CreateBTree(T->left);//构造右子树CreateBTree(T->right);}return 0;
}int main() {Solution solution;TreeNode* root(0);CreateBTree(root);cout<<solution.maxPathSum(root);
}