543. Diameter of Binary Tree

for each node, check the Diameter of subtree where the node is root. this is a candidate Diameter
this node might be on the path of another subtree which determines the max Diameter, so we need to return the max depth contributed by this node

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.diameter = 0

        # return max depth
        # update max diameter
        def dfs(node):
            if not node:
                return 0
            
            left = dfs(node.left)
            right = dfs(node.right)
            self.diameter = max(self.diameter, left+right+1)
            return max(left, right) + 1
        
        dfs(root)
        return self.diameter-1

avoid state

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        _, res = self.helper(root)
        return res - 1
    
    def helper(self, root) -> tuple:
        if not root:
            return 0, 0

        left_depth, left_diameter = self.helper(root.left)
        right_depth, right_diameter = self.helper(root.right)
        diameter = max(left_diameter, right_diameter, left_depth + right_depth + 1)

        return (max(left_depth, right_depth) + 1, diameter)

543. Diameter of Binary Tree - cocoder39/coco39_LC GitHub Wiki