NeetCode #411LC-1522MediumTreesNC Algo100
← Back to All Problems#411 · #1522 · Diameter of N-Ary Tree(N 叉树的直径)
📌 Problem Statement & Constraints
Given the root of an N-ary tree, return its diameter: the length of the longest path between any two nodes, measured in edges. Constraints: the number of nodes is in
[0, 10^4], the depth is at most 1000.💡 Core Algorithmic Approaches
- The same idea as the binary-tree diameter, but a node may have many children.
- For each node, track the two largest child depths; the longest path through the node is their sum.
- The recursion returns
1 + max(child depths)for the parent to use. - Tracking only the top two depths is what keeps the work linear in the number of children.
💻 Benchmark Python3 Implementation
class Solution:
def diameter(self, root: "Optional[Node]") -> int:
self.best = 0
def depth(node: "Optional[Node]") -> int:
if not node:
return 0
top1 = top2 = 0 # two largest child depths
for c in node.children:
d = depth(c)
if d > top1:
top1, top2 = d, top1
elif d > top2:
top2 = d
# the longest path through this node uses its two deepest subtrees
self.best = max(self.best, top1 + top2)
return top1 + 1 # depth for the parent
depth(root)
return self.best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each node is visited once and its children are scanned once.
💾 Space Complexity
O(h) for the recursion stack.
⚠️ Interview Pitfalls & Follow-ups
- Summing all child depths: only the two deepest matter for the path through a node.
- Returning
top1 + top2from the recursion: the parent needs a single depth, so the return value istop1 + 1. - Measuring in nodes rather than edges: the diameter counts edges, so a leaf contributes 0.
- Recomputing depths for every node: O(n^2).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.