Diameter of Binary Tree LeetCode solution in Python

1
# Runtime: 95 ms (Top 16.95%) | Memory: 16.5 MB (Top 10.21%)
2
class Solution:
3
    """
4
    Top Down recursion approach: it is sub optimal
5
    """
6

7
    def __init__(self):
8
        self.max_diameter = 0
9

10
    def diameter(self, root):
11
        if root is None:
12
            return 0
13
        return self.max_depth(root.left) + self.max_depth(root.right)
14

15
    def max_depth(self, root):
16
        if root is None:
17
            return 0
18
        return 1 + max(self.max_depth(root.left), self.max_depth(root.right))
19

20
    def func(self, root):
21
        if root is not None:
22
            diameter = self.diameter(root)
23
            if self.max_diameter < diameter:
24
                self.max_diameter = diameter
25
            self.diameterOfBinaryTree(root.left)
26
            self.diameterOfBinaryTree(root.right)
27

28
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
29
        self.func(root)
30
        return self.max_diameter
31

32
    """
33
    Better Approach: I can try to approach this problem using bottom up recursion
34
    """
35

36
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
37
        self.diameter = 0
38

39
        def fun(root):
40
            if root is None:
41
                return 0
42
            left = fun(root.left)
43
            right = fun(root.right)
44
            if left + right > self.diameter:
45
                self.diameter = left + right
46
            return max(left, right) + 1
47

48
        fun(root)
49
        return self.diameter