543. Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:

Given a binary tree
          1
         / \
        2   3
       / \     
      4   5    
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

Solution

Approach 1: traverse the tree recursively while keeping two parameters: the longest path that pass through the node in the subtree, and the longest path seen everywhere in the subtree.

Code (Python)

Approach 1:

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        if not root:
            return 0
        return self._diameter(root)[1]
    
    def _diameter(self, root):
        if not root.left and not root.right:
            return (0, 0) # (longest path passing through the root, longest path in subtree)
        if root.left and root.right:
            left_local, left_global = self._diameter(root.left)
            right_local, right_global = self._diameter(root.right)
            return (1 + max(left_local, right_local), max(left_global, right_global, 2 + left_local + right_local))
        for child in (root.left, root.right):
            if not child:
                continue
            local_val, global_val = self._diameter(child)
            return (1 + local_val, max(global_val, 1 + local_val))

Code (C++)

Approach 1:

Approach 2: