💬 Discord
Sign In
NeetCode #388LC-543EasyTreesNC 150NC 250
← Back to All Problems

#388 · #543 · Diameter of Binary Tree(二叉树的直径)

📌 Problem Statement & Constraints

Given the root of a binary tree, return the length of its diameter: the number of edges on the longest path between any two nodes. The path need not pass through the root. Constraints: the number of nodes is in [1, 10^4].

💡 Core Algorithmic Approaches

  1. For each node, the longest path through it has left_height + right_height edges.
  2. So compute heights bottom-up and, at each node, update a global maximum with that sum.
  3. The height function returns 1 + max(left, right) while the answer tracks the through-node path.
  4. This single post-order traversal is O(n), far better than computing heights pairwise.

💻 Benchmark Python3 Implementation

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

        def height(node: Optional[TreeNode]) -> int:
            if not node:
                return 0
            l = height(node.left)
            r = height(node.right)
            # the longest path through this node, in edges
            self.best = max(self.best, l + r)
            return 1 + max(l, r)

        height(root)
        return self.best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one post-order traversal.
💾 Space Complexity
O(h) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Assuming the path passes through the root: it need not, which is exactly why the maximum is tracked at every node.
  • Returning l + r + 1: the diameter is measured in edges, so it is l + r.
  • Computing the height of each node separately: O(n^2).
  • Using a mutable default or a class attribute across calls: reset self.best per call, or use a list/nonlocal.