[leetcode] 124. Binary Tree Maximum Path Sum

[leetcode] 124. Binary Tree Maximum Path Sum

Description

Given a non-empty 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 must contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3] 1 / \ 2 3Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7] -10 / \ 9 20 / \ 15 7Output: 42

分析

题目的意思是： 给出一个二叉树，找出节点和最大的路径。

这虽然是一个二叉树遍历的过程，但是结点的值可能为负数，这样我们在计算最大路径值的时候，要注意把求和为负值的分支舍去，保留返回为正值的分支。递归的代码写得非常的简洁漂亮，这种编程模式在刷题的时候经常看见，最好记住。

代码

/** * 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 { int sum=INT_MIN;public: int maxPathSum(TreeNode* root) { preorder(root); return sum; } int preorder(TreeNode* root){ if(!root){ return 0; } int left=max(0,preorder(root->left)); int right=max(0,preorder(root->right)); sum=max(sum,root->val+left+right); return max(left,right)+root->val; }};

参考文献

​​[编程题]binary-tree-maximum-path-sum​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。