Golang bottom-up recursion O(n) solution


  • 0

    This problem can be solved just if you know how to handle recursive "bottom-up" approach. (Normal recursion is performed by "top-down"). By using bottom-up recursion, we don' need to traverse nodes again and again.

    func maxPathSum(root *TreeNode) int {
    	if root == nil {
    		return 0
    	}
    
    	max := math.MinInt32
    	getSum(&max, root)
    	return max
    }
    
    func getSum(max *int, parent *TreeNode) int {
    	leftSum, rightSum := 0, 0
    	if parent.Left == nil {
    		leftSum = 0
    	} else {
    		leftSum = maxint(getSum(max, parent.Left), 0)
    	}
    
    	if parent.Right == nil {
    		rightSum = 0
    	} else {
    		rightSum = maxint(getSum(max, parent.Right), 0)
    	}
    
    	*max = maxint(leftSum+rightSum+parent.Val, *max)
    	return parent.Val + maxint(leftSum, rightSum)
    }
    
    func maxint(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    

Log in to reply
 

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