BinarySearch 0211 Longest Tree Path

Problem statement

https://binarysearch.com/problems/Longest-Tree-Path/

Solution

Equal to Leetcode 0543. Diameter of Binary Tree.

Complexity

It is O(n) for time and O(h) for space.

Code

class Solution:
    def solve(self, root):
        self.diam = 0
        def dfs(root):
            if not root: return (0, 0)
            left = max(dfs(root.left))
            right = max(dfs(root.right))
            self.diam = max(self.diam, left + right)
            return (left + 1, right + 1)
        
        dfs(root)
        return 0 if not root else self.diam + 1