今�Hの国の呵呵君: [LeetCode]Binary Tree Maximum Path Sum

今�Hの国の呵呵君: [LeetCode]Binary Tree Maximum Path Sum

[LeetCode]Binary Tree Maximum Path Sum

注意path可以在tree里的任意节点开始和结束，我们需要用bottom-up的方法，在每一个节点，先递归找到左子树和右子树的一直朝上走的maximum path sum，然后两边与自己的值的和若比现在的max sum大，更新sum。然后从左子树和右子树的最大值挑一个大的与自己的和return上去，注意如果小于等于0的话就直接return0，因为会使得值变得更小。时间复杂度为O(N)

Read full article from 今�Hの国の呵呵君: [LeetCode]Binary Tree Maximum Path Sum