543. Diameter of Binary Tree

Diameter of Binary Tree - LeetCode

Given the root of a binary tree, return 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. The length of a path between two nodes is represented by the number of edges between them.

Example 1: Input: root = [1,2,3,4,5] Output: 3 Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3]. Example 2: Input: root = [1,2] Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 104].
-100 <= Node.val <= 100

  • code
class Solution:
    def dfs(self, node):
        if not node: return 0
        left = 1 + self.dfs(node.left)
        right = 1 + self.dfs(node.right)
        return max(left, right)
        
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        curDia = leftDia = rightDia = 0
        if root.left:
            leftDia = self.diameterOfBinaryTree(root.left)
        if root.right:
            rightDia = self.diameterOfBinaryTree(root.right)
        
        leftDepth = self.dfs(root.left)
        rightDepth = self.dfs(root.right)
        
        curDia = leftDepth + rightDepth
        return max(leftDia, rightDia, curDia)
  • code
class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.diameter = 0

        def longest_path(node):
            if not node:
                return 0
            left_path = longest_path(node.left)
            right_path = longest_path(node.right)

            self.diameter = max(self.diameter, left_path + right_path)

            return max(left_path, right_path) + 1

        longest_path(root)
        return self.diameter
  • code
class Solution:
    def dfs(self, node):
        if not node: return 0
        left = self.dfs(node.left)
        right = self.dfs(node.right)
        self.diameter = max(self.diameter, left + right)
        return max(left, right) + 1
        
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.diameter = 0
        self.dfs(root)
        return self.diameter