What would a top down solution for this problem look like?


  • 1
    M

    I am curious about the top down solution, even if it is not efficient and it gets TLE.


  • 0

    Mine doesn't have TLE. But I'm not sure mine is top down or not.

    3 cases:

    1. greater value of (sum of left child tree + root.val, sum of left child tree)
    2. greater value of (sum of right child tree + root.val, sum of right child tree)
    3. Only root.val

    Of course in case 1, and 2 we need a variable to tracks allSum, consists of (sum of right child tree + sum of left child tree + root.val)

    And we need a long(in case stack overflow) global variable named result, which will be our future output

    Here's code in C#:

    public long result = int.MinValue; //set result
    
    public int MaxPathSum(TreeNode root)
    {
      helper(root);
      return (int) result; //Convert to int
    }
    
     private int helper(TreeNode root)
        {
            if(root == null) return 0;
            
            int left = helper(root.left); 
            int right = helper(root.right);
            int allSum = left + right + root.val;
            
            int MaxWithRoot = Math.Max(Math.Max(left,right) + root.val, root.val);
            
            res = Math.Max(res, Math.Max(MaxWithRoot, allSum));
            return MaxWithRoot;
        }
    

Log in to reply
 

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