Given a binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.
For example:
Given the below binary tree,
1
/ 2 3
Return 6.
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int getMax(TreeNode* root, int &ans) { if(!root) return 0; int leftMax = getMax(root->left, ans), rightMax = getMax(root->right, ans), Max = max(leftMax, rightMax); int curMax = ((leftMax > 0) ? leftMax : 0) + ((rightMax > 0) ? rightMax : 0) + root->val; if(curMax > ans) ans = curMax; if(Max <= 0) return root->val; return Max + root->val; } int maxPathSum(TreeNode* root) { int ans = INT_MIN; getMax(root, ans); return ans; } };
分别求左右子树的最大节点和，若为负，则忽略，若为正，则加上本身的节点值。
124. Binary Tree Maximum Path Sum *HARD* -- 二叉树中节点和最大的路径的节点和
原文：http://www.cnblogs.com/argenbarbie/p/5416168.html