Leetcode # 543. Diameter of Binary Tree

Problem

https://leetcode.com/problems/diameter-of-binary-tree/description/

Solution

Time Complexity: O(len(tree))
Space Complexity: O(max_depth(tree) * len(leaves))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
    stack = [(root, [])]
    leaves = []
    while stack:
      curr, ancestors = stack.pop()
      # ... some process about target
      if curr.left is None and curr.right is None: # is leaf
        leaves.append(ancestors)
          
      for child in [curr.left, curr.right]:
        if child:
          stack.append((child, ancestors + [id(curr)]))
    diameter = max([len(a) for a in leaves])
    for k, a1 in enumerate(leaves):
      for a2 in leaves[k + 1:]:
        for i in range(min(len(a1), len(a2))):
          if a1[i] != a2[i]:
            i -= 1
            break
        path_len = (len(a1) - i) + (len(a2) - i)
        diameter = max(diameter, path_len)
    return diameter

Last Updated on 2024/04/20 by A1go