1
\$\begingroup\$

I am working on one question, Find max path sum from two leaves

Given a binary tree in which each node element contains a number. Find the maximum possible sum from one leaf node to another.

class TreeNode:
    def __init__(self, x=None):
        self.val = x
        self.left = None
        self.right = None

def maxPathSum(root: TreeNode) -> int:
    res = float('-inf')

    def traversal(node, pathsum):
        nonlocal res

        if node is None:
            return 0
        if node.left is None and node.right is None:
            return node.val
        ln_value = traversal(node.left, pathsum)
        rn_value = traversal(node.right, pathsum)
        if node.left is not None and node.right is not None:
            res = max(res, node.val + ln_value + rn_value)
            return max(ln_value, rn_value) + node.val

        if node.left is None:
            return rn_value + node.val
        else:
            return ln_value + node.val

    traversal(root, res)
    return res
\$\endgroup\$
  • \$\begingroup\$ This code won't work on the example given behind your link. (Or any example with a half-full node.) Perhaps you should debug it more before asking for a review. \$\endgroup\$ – Austin Hastings Apr 21 '19 at 20:00
  • \$\begingroup\$ my bad post the wrong code. updated already. any good idea how to handle to res if not using nonlocal? \$\endgroup\$ – A.Lee Apr 21 '19 at 21:10
  • \$\begingroup\$ Return a tuple. And it still doesn't work, I think. What if your tree is (10, (-1), (-1))? \$\endgroup\$ – Austin Hastings Apr 21 '19 at 22:54
  • \$\begingroup\$ what do you mean return a tuple? \$\endgroup\$ – A.Lee Apr 22 '19 at 19:47
  • \$\begingroup\$ A tuple is a built-in Python type. There is syntactic sugar for constructing them, so you can do something like: return (1, 2) \$\endgroup\$ – Austin Hastings Apr 22 '19 at 19:49

Browse other questions tagged or ask your own question.