题解 | #二叉树中的最大路径和#DFS遍历(返回分支最大的值:二种情况本身节点值或加上两侧最大值)
二叉树中的最大路径和
http://www.nowcoder.com/practice/da785ea0f64b442488c125b441a4ba4a
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 * @return int整型 */ int maxPathSum(TreeNode* root) { // write code here if(root == NULL) return 0; maxValue = -1e9; dfs(root); return maxValue; } int dfs(TreeNode* root) { if(root==NULL) return 0; int l = dfs(root->left); int r = dfs(root->right); maxValue = max(maxValue,root->val); if(l > 0) maxValue = max(maxValue,root->val+l); if(r > 0) maxValue = max(maxValue,root->val+r); if(l > 0 && r > 0) maxValue = max(maxValue,root->val+r+l); if(max(l,r) > 0) return max(l,r)+root->val; else return root->val; } private: int maxValue; };