专栏首页米扑专栏【leetcode】Binary Tree Maximum Path Sum

【leetcode】Binary Tree Maximum Path Sum

Question :  

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.

Anwser 1 :  

/**
  * 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 calLen(TreeNode *root, int &len)
     {
         if (root == NULL)
         {
             len = 0;
             return 0;
         }
         
         if (root->left == NULL && root->right == NULL)
         {
             len = root->val;
             return root->val;
         }
         
         int leftPath, rightPath;
         int leftLen;
         if (root->left)
             leftLen = calLen(root->left, leftPath);
         else
         {
             leftLen = INT_MIN;
             leftPath = 0;
         }
         
         int rightLen;
         if (root->right)
             rightLen = calLen(root->right, rightPath);
         else
         {
             rightLen = INT_MIN;
             rightPath = 0;
         }
         
         len = max(max(leftPath, rightPath) + root->val, root->val);
         int maxLen = max(root->val, max(leftPath + rightPath + root->val, 
             max(leftPath + root->val, rightPath + root->val)));
         
         return max(max(leftLen, rightLen), maxLen);
     }
     
     int maxPathSum(TreeNode *root) {
         // Start typing your C/C++ solution below
         // DO NOT write int main() function
         int len;
         return calLen(root, len);
     }
 };

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【leetcode】Sum Root to Leaf Numbers

    Given a binary tree containing digits from 0-9 only, each root-to-leaf path coul...

    阳光岛主
  • Linux / MacOS 修改 ls 显示年月日的时间格式

    本文参考转自米扑博客:Linux / MacOS 修改 ls 显示年月日的时间格式

    阳光岛主
  • Linux 用Sendmail架设Mail服务器

      人们在互联网上最常使用的就是电子邮件了,很多企业用户也经常使用免费的电子邮件系统。今天我就给大家介绍一种在Red Hat Linux 9.0环境下运行的邮件...

    阳光岛主
  • 第91场周赛

    题解:根据描述,有三种类型的钞票,如果是5元的,可以直接收,如果是10元的,那么则需要给对方一张5元的,收到一张10元的,如果是20元的,那么需要给对方一张10...

    用户1145562
  • LeetCode 938 Range Sum of BST

    给予一颗二叉搜索树, 返回区间 L - R 之间的所有值的总和. 二叉搜索树中没有重复值.

    一份执着✘
  • MySQL 连接

    给予一颗二叉搜索树, 返回区间 L - R 之间的所有值的总和. 二叉搜索树中没有重复值.

    一份执着✘
  • MySQL之mysqladmin客户端

    在我们日常操作中,drop操作应该谨慎一些,可以看到,mysql也友好的给出了提醒。

    AsiaYe
  • c++ LeetCode (网易面试题和链表以及树篇) 五道算法例题代码详解(三)

    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

    徐飞机
  • 贪心算法-LeetCode 134、111(递归算法,异或性质,贪心)

    对于swap函数使用中间变量的形式大家都不陌生了,但是对于面试官来说这种方法不出奇,并不是面试官想要的!有没有不使用中间变量的呢? 在swap2函数中,我们可以...

    算法工程师之路
  • LeetCode 450: 删除二叉搜索树中的节点 Delete Node in a BST

    给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节...

    爱写bug

扫码关注云+社区

领取腾讯云代金券