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,

Return 6 .

找出任意两个节点之间的路径，并且该路径的值之和最大。

PS：关键在于递归函数的返回值，应该返回该节点的任意子节点到该节点父节点之间路径的最大值，即root->l返回的值应该为root->l的任意子节点到root能得到的最大值-root->val。同时在遍历时时刻检查sum与max的大小并更新max的值。

 /**

  * Definition for binary tree

  * struct TreeNode {

  *     int val;

  *     TreeNode *left;

  *     TreeNode *right;

  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

  * };

  */

 class Solution {

 public:

     int maxPathSum(TreeNode *root) {

         res=INT_MIN;

         dfs(root);

         return res;

     }

     int dfs(TreeNode *root){

         if(root==NULL){

             return ;

         }

         int sum=root->val;

         int l=dfs(root->left);

         int r=dfs(root->right);

         if(l>) sum+=l;

         if(r>) sum+=r;

         res=max(res,sum);

         int tmp=max(l,r);

         return tmp>?tmp+root->val:root->val;

     }

     int res;

 };