543. Diameter of Binary Tree

Problem Statement

link: LeetCode.cn 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:

Input: root = [1,2,3,4,5] Output: 3

Input: root = [1,2] Output: 1

Solution Approach

This problem can be efficiently solved using depth-first search (DFS) traversal of the binary tree.

Algorithm

1. Define a DFS function that calculates the depth of the left and right subtrees for each node.
2. During the DFS traversal, update a global variable to store the maximum diameter encountered so far.
3. Return the maximum depth of the left or right subtree plus one for each node, and update the global diameter variable with the sum of left and right subtree depths if it’s greater.

Implement

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

    
    

Twitter  facebook  Email