首页 > 代码库 > [LeetCode]Binary Tree Maximum Path Sum
[LeetCode]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; }//if maxSum = 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; }//if if(rightMax > 0){ curMax += rightMax; }//if maxSum = 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 =http://www.mamicode.com/= -1){>[LeetCode]Binary Tree Maximum Path Sum
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。