How to optimize the following code to get more efficient algorithm


  • 0
    D

    Definition for a binary tree node

    class TreeNode:

    def init(self, x):

    self.val = x

    self.left = None

    self.right = None

    class Solution:
    # @param root, a tree node
    # @return an integer

    def maxPathSum(self, root):
        if root==None:
            return 0
        sum1=self.maxPathSum(root.left)
        sum2=self.maxPathSum(root.right)
        sum3=root.val+self.rootleafMaxPath(root.left)+self.rootleafMaxPath(root.right)
        sum4=self.rootleafMaxPath(root)
        return max(sum1,sum2,sum3,sum4)
        
    def rootleafMaxPath(self,root):
        if root==None:
            return 0
        sum1=self.rootleafMaxPath(root.left)
        sum2=self.rootleafMaxPath(root.right)
        sum=max(root.val,max(sum1,sum2)+root.val)
        return sum

  • 0
    N

    try using hashmap to store intermediate result


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.