原题
已知一颗二叉树，找到从根节点到任意节点的最大路径和
已知下面一颗二叉树
1
/ \
2 3
返回4. (1->3)
解题思路
- Divide and Conquer
- 借助一个helper函数，从根节点向下分裂，每一层返回左右儿子中的最大值与当前节点的值，层层递归
完整代码
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
this.val = val
this.left, this.right = None, None
"""
class Solution:
"""
@param root the root of binary tree.
@return an integer
"""
def maxPathSum2(self, root):
return self.helper(root)
def helper(self, root):
if not root:
return 0
left = self.helper(root.left)
right = self.helper(root.right)
return max(left, right) + root.val
