首页 > 代码库 > LeetCode--Binary Tree Maximum Path Sum
LeetCode--Binary Tree Maximum Path Sum
递归，dfs
这里返回值是一个pair<int,int>，first表示两个子树的不经过当前root的最大pathsum；second表示两个子树的，以root->left和root->right为路径起始节点的路径的最大值
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 class Solution {11 public:12 int maxPathSum(TreeNode *root) {13 pair<int,int> res = dfs(root);14 return res.first;15 }16 pair<int,int> dfs(TreeNode *root)17 {18 if(root == NULL)19 {20 return make_pair(0,0);21 }22 pair<int,int> left = dfs(root->left);23 pair<int,int> right = dfs(root->right);24 int leftCrossMax = left.first;25 int rightCrossMax = right.first;26 27 int leftMax = left.second > 0?left.second:0;28 int rightMax = right.second > 0?right.second:0;29 30 int maxNoCross = INT_MIN;31 if(root->left != NULL)32 {33 maxNoCross = max(maxNoCross,leftCrossMax);34 }35 if(root->right != NULL)36 {37 maxNoCross = max(maxNoCross,rightCrossMax);38 }39 int maxCross = leftMax+rightMax+root->val;40 int maxSum = max(maxCross,maxNoCross);41 42 int child = max(leftMax,rightMax);43 int maxChild = child > 0?child+root->val:root->val;44 return make_pair(maxSum,maxChild);45 }46 };
LeetCode--Binary Tree Maximum Path Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。