Hi, here’s your problem today. This problem was recently asked by Facebook:
You are given the root of a binary tree. Find the path between 2 nodes that maximizes the sum of all the nodes in the path, and return the sum. The path does not necessarily need to go through the root.
class Node: def init(self, val): self.val = val self.left = None self.right = None
def maxPathSum(root):
Fill this in.
(* denotes the max path)
*10
/ \
*2 *10
/ \ \
*20 1 -25
/ \
3 4
root = Node(10) root.left = Node(2) root.right = Node(10) root.left.left = Node(20) root.left.right = Node(1) root.right.right = Node(-25) root.right.right.left = Node(3) root.right.right.right = Node(4) print maxPathSum(root)