For each node keep track of 2 things:
- local max including node itself
- max between left and right subtree
#2 will keep track of the longest path with the node as part of the sequence while #1 keep track of the longest path curving around the node.
class Solution(object): def helper(self, node): if not node: return 0, 0 left, lMax = self.helper(node.left) right, rMax = self.helper(node.right) return max(left, right)+1, max(lMax, rMax, left+right) def diameterOfBinaryTree(self, root): """ :type root: TreeNode :rtype: int """ return self.helper(root)