Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1863941
  • 博文数量: 211
  • 博客积分: 464
  • 博客等级: 下士
  • 技术积分: 3794
  • 用 户 组: 普通用户
  • 注册时间: 2011-01-24 18:25
个人简介

阿弥陀佛

文章分类

全部博文(211)

文章存档

2020年(2)

2019年(3)

2018年(5)

2017年(6)

2016年(10)

2015年(9)

2014年(73)

2013年(90)

2012年(13)

分类: C/C++

2015-08-15 09:42:43

传送门: />
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.



/**
 * 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 max=-31;
    int maxPathSum1(TreeNode* root){
        int mlocal=0,v,v1,v2;
        
        if(root == NULL)
            return 0;
        v = root->val;
      
        mlocal = v;
        v1 = maxPathSum1(root->left);
        mlocal = v1+v;
            
        v2 = maxPathSum1(root->right);
        
 
        mlocal = v1+v+v2;
        if(mlocal>max)
            max = mlocal;
        if(v1>v2)
            v=root->val+v1;
        else v=root->val+v2;
        if(v<0)
            return 0;
        return v;
        
    }
    
    int maxPathSum(TreeNode* root) {
        maxPathSum1(root);
        return max;
    }
};
阅读(2564) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~