LeetCode 559 N 叉树直径详解一次 DFS 同时求解高度与最长路径附高度法与深度法双解法【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文以 LeetCode 559「N-ary Tree Diameter」为主线完整讲解如何用一次递归遍历同时求出 N 叉树中任意两节点间的最长路径直径先给出基于高度向下到叶的经典解法再给出基于深度距根距离的等价变体并对照本仓库中 543 题二叉树直径的多语言实现说明二者背后是同一套「边求高度、边更新全局最优」的 DFS 范式。读完后你能独立写出、调试并讲解这两种解法并理解二叉树与 N 叉树场景下代码的异同。本仓库articles/目录下的解题文章遵循统一的撰写规范见 articles/README.md给出至少一种与官方讲解一致的解法、完整覆盖多种语言的实现并标注时间与空间复杂度。articles/diameter-of-n-ary-tree.md 正是这一规范的体现下文即在完整继承其内容的基础上做源码级扩充。前置知识在动手之前建议先熟悉以下三个概念原文档 Prerequisites 部分N 叉树N-ary Trees每个节点可以有任意多个子节点的树结构。LeetCode 中该题的节点定义为class Node: def __init__(self, valNone, childrenNone): self.val val self.children children or []与二叉树的left/right不同这里统一用children列表表达所有子节点这也是后续所有语言实现里都围绕node.children遍历的原因。递归Recursion两种解法都依赖递归遍历来计算各子树的高度/深度时间复杂度天然为 $O(N)$。树高 vs 树深Tree Height vs Depth高度是「从当前节点向下到叶子」的最长路径长度深度是「从根到当前节点」的路径长度。二者方向相反原文档特意将两种解法分拆就是为了对比这两个视角。问题定义与核心洞察N 叉树的直径定义为树中任意两个节点之间最长路径的边数节点数减一。核心洞察可以概括为一句话任意一条最长路径必然存在一个「最高点」最靠近根的节点路径从该点向下经过它的两个不同子分支分别到达两个叶子。因此经过某个节点的最长路径长度 该节点所有子节点中最大的两个高度之和。只要自底向上递归地求出每个子树的高度并在每个节点处用「前两大高度之和」更新全局最大值遍历结束后全局最大值就是答案。这也正是本仓库 hints/binary-tree-diameter.md 中针对 543 题给出的提示思路For any given node, the longest path that passes through it is the sum of the height of its left subtree and the height of its right subtree在 N 叉树上推广为「取前两大子树高度」。解法一基于高度的解法Distance with Height节点高度定义为从该节点向下到叶子的最长路径长度。直觉树的直径是任意两节点间的最长路径。这条路径必然以某个节点作为最高点在该点向下分叉进入两个不同子树。于是「经过任意节点的最长路径 其子节点中前两大高度之和」。递归计算高度并沿途追踪最大路径长度即得直径。算法步骤定义递归函数返回某节点的高度到其最深叶子后代的最长路径。叶子节点无子节点返回高度0。对每个节点遍历其子节点维护前两大高度max_height_1、max_height_2。每处理完一个子节点就用当前的前两大高度之和更新全局最大直径。返回max_height_1即本节点高度 最矮分支深度 1 的等价表达实现中用子树高度 1 累积。遍历整棵树后返回记录到的最大直径。多语言实现完整继承原文档Python—— 用闭包变量diameter携带全局最优值避免使用成员变量class Solution: def diameter(self, root: Node) - int: diameter 0 def height(node): return the height of the node nonlocal diameter if len(node.children) 0: return 0 # select the top two heights max_height_1, max_height_2 0, 0 for child in node.children: parent_height height(child) 1 if parent_height max_height_1: max_height_1, max_height_2 parent_height, max_height_1 elif parent_height max_height_2: max_height_2 parent_height # calculate the distance between the two farthest leaves nodes. distance max_height_1 max_height_2 diameter max(diameter, distance) return max_height_1 height(root) return diameterJava—— 全局最优值用成员字段diameter保存递归函数height负责更新class Solution { protected int diameter 0; /** * return the height of the node */ protected int height(Node node) { if (node.children.size() 0) return 0; // select the top two largest heights int maxHeight1 0, maxHeight2 0; for (Node child : node.children) { int parentHeight height(child) 1; if (parentHeight maxHeight1) { maxHeight2 maxHeight1; maxHeight1 parentHeight; } else if (parentHeight maxHeight2) { maxHeight2 parentHeight; } // calculate the distance between the two farthest leaves nodes. int distance maxHeight1 maxHeight2; this.diameter Math.max(this.diameter, distance); } return maxHeight1; } public int diameter(Node root) { this.diameter 0; height(root); return diameter; } }C—— 与 Java 结构一致用protected成员保存中间状态class Solution { protected: int dia 0; int height(Node* node) { if (node-children.size() 0) return 0; int maxHeight1 0, maxHeight2 0; for (Node* child : node-children) { int parentHeight height(child) 1; if (parentHeight maxHeight1) { maxHeight2 maxHeight1; maxHeight1 parentHeight; } else if (parentHeight maxHeight2) { maxHeight2 parentHeight; } int distance maxHeight1 maxHeight2; dia max(dia, distance); } return maxHeight1; } public: int diameter(Node* root) { dia 0; height(root); return dia; } };JavaScript—— 闭包捕获diameter箭头函数递归class Solution { /** * param {_Node} root * return {number} */ diameter(root) { let diameter 0; const height (node) { if (node.children.length 0) return 0; let maxHeight1 0, maxHeight2 0; for (const child of node.children) { const parentHeight height(child) 1; if (parentHeight maxHeight1) { maxHeight2 maxHeight1; maxHeight1 parentHeight; } else if (parentHeight maxHeight2) { maxHeight2 parentHeight; } const distance maxHeight1 maxHeight2; diameter Math.max(diameter, distance); } return maxHeight1; }; height(root); return diameter; } }C#public class Solution { private int diameter 0; private int Height(Node node) { if (node.children.Count 0) return 0; int maxHeight1 0, maxHeight2 0; foreach (Node child in node.children) { int parentHeight Height(child) 1; if (parentHeight maxHeight1) { maxHeight2 maxHeight1; maxHeight1 parentHeight; } else if (parentHeight maxHeight2) { maxHeight2 parentHeight; } int distance maxHeight1 maxHeight2; diameter Math.Max(diameter, distance); } return maxHeight1; } public int Diameter(Node root) { diameter 0; Height(root); return diameter; } }Go—— 自引用匿名函数实现递归闭包注意var height func(node *Node) int必须先声明再赋值func diameter(root *Node) int { dia : 0 var height func(node *Node) int height func(node *Node) int { if len(node.Children) 0 { return 0 } maxHeight1, maxHeight2 : 0, 0 for _, child : range node.Children { parentHeight : height(child) 1 if parentHeight maxHeight1 { maxHeight2 maxHeight1 maxHeight1 parentHeight } else if parentHeight maxHeight2 { maxHeight2 parentHeight } distance : maxHeight1 maxHeight2 if distance dia { dia distance } } return maxHeight1 } height(root) return dia }Kotlinclass Solution { private var diameter 0 private fun height(node: Node): Int { if (node.children.isEmpty()) return 0 var maxHeight1 0 var maxHeight2 0 for (child in node.children) { val parentHeight height(child) 1 if (parentHeight maxHeight1) { maxHeight2 maxHeight1 maxHeight1 parentHeight } else if (parentHeight maxHeight2) { maxHeight2 parentHeight } val distance maxHeight1 maxHeight2 diameter maxOf(diameter, distance) } return maxHeight1 } fun diameter(root: Node): Int { diameter 0 height(root) return diameter } }Swift—— 嵌套函数天然形成闭包var diameter被递归函数捕获class Solution { func diameter(_ root: Node) - Int { var diameter 0 func height(_ node: Node) - Int { if node.children.isEmpty { return 0 } var maxHeight1 0, maxHeight2 0 for child in node.children { let parentHeight height(child) 1 if parentHeight maxHeight1 { maxHeight2 maxHeight1 maxHeight1 parentHeight } else if parentHeight maxHeight2 { maxHeight2 parentHeight } let distance maxHeight1 maxHeight2 diameter max(diameter, distance) } return maxHeight1 } height(root) return diameter } }Rust—— 所有权语义下全局最优值通过mut i32参数显式传递不能像 Python/Kotlin 那样隐式捕获可变闭包变量// Definition: struct Node { val: i32, children: VecNode } struct Solution; impl Solution { pub fn diameter(root: Node) - i32 { let mut diameter 0; fn height(node: Node, diameter: mut i32) - i32 { if node.children.is_empty() { return 0; } let (mut max_height1, mut max_height2) (0, 0); for child in node.children { let parent_height height(child, diameter) 1; if parent_height max_height1 { max_height2 max_height1; max_height1 parent_height; } else if parent_height max_height2 { max_height2 parent_height; } let distance max_height1 max_height2; *diameter (*diameter).max(distance); } max_height1 } height(root, mut diameter); diameter } }复杂度时间复杂度$O(N)$ —— 每个节点恰好被访问一次。空间复杂度$O(N)$ —— 递归调用栈在最坏情况下树退化为链达到 $O(N)$。其中 $N$ 为树的节点数。解法二基于深度的解法Distance with Depth节点深度定义为该节点到根节点的路径长度。直觉不追踪「向下的距离」高度而是追踪「距根的距离」深度。经过某节点的路径长度 其两个最深叶子路径的深度之和减去当前节点深度的两倍——因为「下到一个叶子、回到当前节点、再到另一个叶子」中当前节点以下的路径段被重复计了两次。算法步骤定义递归函数参数为节点及其当前深度返回其子树内叶子的最大深度。叶子节点直接返回当前深度curr_depth。遍历子节点维护前两大深度max_depth_1、max_depth_2。注意初始化差异max_depth_1 curr_depthmax_depth_2 0。这一步处理了「节点只有一个深子分支」的退化情况——第二个值兜底为当前深度保证distance不会低估单分支路径。经过该节点的直径候选值max_depth_1 max_depth_2 - 2 * curr_depth更新全局直径。向父调用返回max_depth_1本点子树的最深叶子深度。多语言实现完整继承原文档Pythonclass Solution: def diameter(self, root: Node) - int: diameter 0 def maxDepth(node, curr_depth): return the maximum depth of leaves nodes descending from the current node nonlocal diameter if len(node.children) 0: return curr_depth # select the top 2 depths from its children max_depth_1, max_depth_2 curr_depth, 0 for child in node.children: depth maxDepth(child, curr_depth1) if depth max_depth_1: max_depth_1, max_depth_2 depth, max_depth_1 elif depth max_depth_2: max_depth_2 depth # calculate the distance between the two farthest leaves nodes distance max_depth_1 max_depth_2 - 2 * curr_depth diameter max(diameter, distance) return max_depth_1 maxDepth(root, 0) return diameterJavaclass Solution { protected int diameter 0; /** * return the maximum depth of leaves nodes descending from the given node */ protected int maxDepth(Node node, int currDepth) { if (node.children.size() 0) return currDepth; // select the top two largest depths int maxDepth1 currDepth, maxDepth2 0; for (Node child : node.children) { int depth maxDepth(child, currDepth 1); if (depth maxDepth1) { maxDepth2 maxDepth1; maxDepth1 depth; } else if (depth maxDepth2) { maxDepth2 depth; } // calculate the distance between the two farthest leaves nodes. int distance maxDepth1 maxDepth2 - 2 * currDepth; this.diameter Math.max(this.diameter, distance); } return maxDepth1; } public int diameter(Node root) { this.diameter 0; maxDepth(root, 0); return diameter; } }Cclass Solution { protected: int diameter 0; /** * return the maximum depth of leaves nodes descending from the given node */ int maxDepth(Node* node, int currDepth) { if (node-children.size() 0) return currDepth; // select the top two largest depths int maxDepth1 currDepth, maxDepth2 0; for (Node* child : node-children) { int depth maxDepth(child, currDepth 1); if (depth maxDepth1) { maxDepth2 maxDepth1; maxDepth1 depth; } else if (depth maxDepth2) { maxDepth2 depth; } // calculate the distance between the two farthest leaves nodes. int distance maxDepth1 maxDepth2 - 2 * currDepth; this-diameter max(this-diameter, distance); } return maxDepth1; } public: int diameter(Node* root) { this-diameter 0; maxDepth(root, 0); return diameter; } };JavaScript—— 注意此解法在 JS 中把直径更新放在了for循环之外每次调用只算一次与解法一的写法略有差异但结果等价class Solution { /** * param {_Node} root * return {number} */ diameter(root) { let diameter 0; const maxDepth (node, curr_depth) { /* return the maximum depth of leaves nodes descending from the current node */ if (node.children.length 0) { return curr_depth; } // select the top 2 depths from its children let max_depth_1 curr_depth, max_depth_2 0; for (const child of node.children) { const depth maxDepth(child, curr_depth 1); if (depth max_depth_1) { max_depth_2 max_depth_1; max_depth_1 depth; } else if (depth max_depth_2) { max_depth_2 depth; } } // calculate the distance between the two farthest leaves nodes const distance max_depth_1 max_depth_2 - 2 * curr_depth; diameter Math.max(diameter, distance); return max_depth_1; }; maxDepth(root, 0); return diameter; } }C#public class Solution { private int diameter 0; private int MaxDepth(Node node, int currDepth) { if (node.children.Count 0) return currDepth; int maxDepth1 currDepth, maxDepth2 0; foreach (Node child in node.children) { int depth MaxDepth(child, currDepth 1); if (depth maxDepth1) { maxDepth2 maxDepth1; maxDepth1 depth; } else if (depth maxDepth2) { maxDepth2 depth; } int distance maxDepth1 maxDepth2 - 2 * currDepth; diameter Math.Max(diameter, distance); } return maxDepth1; } public int Diameter(Node root) { diameter 0; MaxDepth(root, 0); return diameter; } }Gofunc diameter(root *Node) int { dia : 0 var maxDepth func(node *Node, currDepth int) int maxDepth func(node *Node, currDepth int) int { if len(node.Children) 0 { return currDepth } maxDepth1, maxDepth2 : currDepth, 0 for _, child : range node.Children { depth : maxDepth(child, currDepth1) if depth maxDepth1 { maxDepth2 maxDepth1 maxDepth1 depth } else if depth maxDepth2 { maxDepth2 depth } distance : maxDepth1 maxDepth2 - 2*currDepth if distance dia { dia distance } } return maxDepth1 } maxDepth(root, 0) return dia }Kotlinclass Solution { private var diameter 0 private fun maxDepth(node: Node, currDepth: Int): Int { if (node.children.isEmpty()) return currDepth var maxDepth1 currDepth var maxDepth2 0 for (child in node.children) { val depth maxDepth(child, currDepth 1) if (depth maxDepth1) { maxDepth2 maxDepth1 maxDepth1 depth } else if (depth maxDepth2) { maxDepth2 depth } val distance maxDepth1 maxDepth2 - 2 * currDepth diameter maxOf(diameter, distance) } return maxDepth1 } fun diameter(root: Node): Int { diameter 0 maxDepth(root, 0) return diameter } }Swiftclass Solution { func diameter(_ root: Node) - Int { var diameter 0 func maxDepth(_ node: Node, _ currDepth: Int) - Int { if node.children.isEmpty { return currDepth } var maxDepth1 currDepth, maxDepth2 0 for child in node.children { let depth maxDepth(child, currDepth 1) if depth maxDepth1 { maxDepth2 maxDepth1 maxDepth1 depth } else if depth maxDepth2 { maxDepth2 depth } let distance maxDepth1 maxDepth2 - 2 * currDepth diameter max(diameter, distance) } return maxDepth1 } maxDepth(root, 0) return diameter } }Rust// Definition: struct Node { val: i32, children: VecNode } struct Solution; impl Solution { pub fn diameter(root: Node) - i32 { let mut diameter 0; fn max_depth(node: Node, curr_depth: i32, diameter: mut i32) - i32 { if node.children.is_empty() { return curr_depth; } let (mut max_depth1, mut max_depth2) (curr_depth, 0); for child in node.children { let depth max_depth(child, curr_depth 1, diameter); if depth max_depth1 { max_depth2 max_depth1; max_depth1 depth; } else if depth max_depth2 { max_depth2 depth; } let distance max_depth1 max_depth2 - 2 * curr_depth; *diameter (*diameter).max(distance); } max_depth1 } max_depth(root, 0, mut diameter); diameter } }复杂度时间复杂度$O(N)$空间复杂度$O(N)$ —— 递归栈深度每次调用还携带一个curr_depth参数不改变量级。两种解法对比维度高度法解法一深度法解法二递归返回值本节点到最深叶子的高度相对值本子树最深叶子的绝对深度递归参数仅节点节点 当前深度直径候选式max_height_1 max_height_2max_depth_1 max_depth_2 - 2 * curr_depth前两大初始值(0, 0)(curr_depth, 0)兜底单分支情形直观程度更简洁面试首选强调「绝对位置」视角便于理解 LCA 类推导两种解法数学上完全等价设某节点深度为 $d$第 $i$ 个子分支的最深叶子深度为 $d_i$则其相对高度为 $d_i - d$候选直径 $(d_i - d) (d_j - d) d_i d_j - 2d$正好是深度法的表达式。常见错误Common Pitfalls原文档总结了三个典型陷阱逐一附对照代码错误一只考虑经过根节点的路径直径不必然经过根最长路径可能完全位于某棵子树内部。必须在每个节点处更新全局最大直径而不是只在根处计算# Wrong: Only checking diameter at root level def diameter(root): heights [height(child) for child in root.children] heights.sort(reverseTrue) return heights[0] heights[1] if len(heights) 2 else 0 # Correct: Track max diameter across all nodes def diameter(root): max_diameter 0 def height(node): nonlocal max_diameter # ... update max_diameter at every node height(root) return max_diameter错误二混淆高度与深度的定义高度向下到叶返回的是「相对距离」深度距根是「绝对距离」通常以参数传入。混用二者会得到错误的路径长度# Using height: returns longest path DOWN from node def height(node): if not node.children: return 0 return 1 max(height(child) for child in node.children) # Using depth: distance FROM ROOT passed as parameter def maxDepth(node, curr_depth): if not node.children: return curr_depth # Returns absolute depth return max(maxDepth(child, curr_depth 1) for child in node.children)错误三只追踪单一最大高度计算经过某节点的直径必须用到「前两大」子树高度。只维护一个最大值会丢掉第二分支直接漏掉答案# Wrong: Only tracking one maximum max_height 0 for child in node.children: max_height max(max_height, height(child) 1) diameter max_height # Missing the second branch! # Correct: Track top two heights max_height_1, max_height_2 0, 0 for child in node.children: h height(child) 1 if h max_height_1: max_height_1, max_height_2 h, max_height_1 elif h max_height_2: max_height_2 h diameter max_height_1 max_height_2源码佐证N 叉树直径与二叉树直径的同一范式本仓库中 559 题本身没有独立的源码文件但同主题的 543「二叉树直径」在多种语言下都有完整实现它们是理解上述 N 叉树解法最好的「退化特例」对照。从源码结构看两者是同一套「一次 DFS返回高度 全局更新」范式Python 对照python/0543-diameter-of-binary-tree.pyclass Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) - int: res 0 def dfs(root): nonlocal res if not root: return 0 left dfs(root.left) right dfs(root.right) res max(res, left right) return 1 max(left, right) dfs(root) return res对照 559 高度法可以看到清晰的推广关系二叉树里「子节点集合」恰好只有left、right两个因此「前两大高度之和」直接写成left right无需维护 top-two 变量递归返回1 max(left, right)对应 N 叉树中的「最矮分支 1」。C 对照cpp/0543-diameter-of-binary-tree.cppclass Solution { public: int diameterOfBinaryTree(TreeNode* root) { int result 0; dfs(root, result); return result; } private: int dfs(TreeNode* root, int result) { if (root NULL) { return 0; } int left dfs(root-left, result); int right dfs(root-right, result); result max(result, left right); return 1 max(left, right); } };这里用引用参数int result传递全局最优值与 559 Rust 解法的mut i32参数手法一致——在无成员变量可用的场景下「按引用传出全局状态」是跨语言的通用技巧。文件头注释也标明了同样的复杂度结论Time: O(n) / Space: O(n)。Java 对照java/0543-diameter-of-binary-tree.java给出了另一种计数习惯空节点返回-1非空节点先对左右各1于是left right就是经过当前节点的边数class Solution { int result -1; public int diameterOfBinaryTree(TreeNode root) { dfs(root); return result; } private int dfs(TreeNode current) { if (current null) { return -1; } int left 1 dfs(current.left); int right 1 dfs(current.right); result Math.max(result, (left right)); return Math.max(left, right); } }这说明「空节点返回 0 还是 -1」是同一算法的两种偏移写法只要「高度递推」与「直径累加」两处偏移保持一致结果就正确。这正是上文「错误二混淆高度/深度定义」要防范的偏移一致性问题的现实例子。Go 对照go/0543-diameter-of-binary-tree.go则用了指针参数*int携带全局最大值并自定义了max辅助函数该实现基于 Go 1.20 之前的版本未使用标准库泛型max可作为环境兼容性的注意点func diameterOfBinaryTree(root *TreeNode) int { maxLength : 0 dfs(root, maxLength) return maxLength } func dfs(t *TreeNode, maxLength *int) int { if t nil { return 0 } left : dfs(t.Left, maxLength) right : dfs(t.Right, maxLength) *maxLength max(*maxLength, leftright) return max(left, right) 1 }而仓库中 hints/binary-tree-diameter.md 的提示链与 559 文档的推导完全同构先指出暴力逐节点算左右高度是 $O(N^2)$再引导「能否在计算树高的同一次遍历中顺便求出直径」最后落点在「用全局变量在遍历中更新最大直径」。可以推断掌握 543 的这组提示与实现后559 的全部代码改动只有两处把left/right两个分支替换为对children的循环以及把「两个值直接相加」升级为「维护 top-two」。延伸阅读围绕 N 叉树数据结构本仓库articles/目录还有几篇可直接衔接的主题文章构成完整的学习路径N 叉树后序遍历 —— 熟悉children结构的递归/迭代遍历克隆 N 叉树 —— N 叉树的深拷贝实现将 N 叉树编码为二叉树 —— N 叉与二叉表示之间的双向转换N 叉树的序列化与反序列化 —— 用字符串承载任意叉数的树查找 N 叉树的根节点 —— N 叉树上的图论技巧。二叉树侧的直径题解文章 articles/binary-tree-diameter.md 与本文的「源码佐证」一节相互呼应适合放在一起复习「高度 全局更新」这一通用 DFS 模式。小结直径 任意节点处「前两大子分支高度之和」的全局最大值一次后序遍历即可求解时间与空间均为 $O(N)$。高度法与深度法数学等价区别仅在返回值语义相对高度 vs 绝对深度与偏移处理实现时须保证两处偏移一致。三个高频陷阱只在根处更新、混用高度/深度、只维护单一最大值。543二叉树是该问题「children 恰好两个」的特例仓库中的 0543 多语言实现 与 hints/binary-tree-diameter.md 可作为退化对照帮助验证自己对 N 叉版本每行代码的理解。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 559 N 叉树直径详解：一次 DFS 同时求解高度与最长路径，附高度法与深度法双解法
LeetCode 559 N 叉树直径详解一次 DFS 同时求解高度与最长路径附高度法与深度法双解法【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文以 LeetCode 559「N-ary Tree Diameter」为主线完整讲解如何用一次递归遍历同时求出 N 叉树中任意两节点间的最长路径直径先给出基于高度向下到叶的经典解法再给出基于深度距根距离的等价变体并对照本仓库中 543 题二叉树直径的多语言实现说明二者背后是同一套「边求高度、边更新全局最优」的 DFS 范式。读完后你能独立写出、调试并讲解这两种解法并理解二叉树与 N 叉树场景下代码的异同。本仓库articles/目录下的解题文章遵循统一的撰写规范见 articles/README.md给出至少一种与官方讲解一致的解法、完整覆盖多种语言的实现并标注时间与空间复杂度。articles/diameter-of-n-ary-tree.md 正是这一规范的体现下文即在完整继承其内容的基础上做源码级扩充。前置知识在动手之前建议先熟悉以下三个概念原文档 Prerequisites 部分N 叉树N-ary Trees每个节点可以有任意多个子节点的树结构。LeetCode 中该题的节点定义为class Node: def __init__(self, valNone, childrenNone): self.val val self.children children or []与二叉树的left/right不同这里统一用children列表表达所有子节点这也是后续所有语言实现里都围绕node.children遍历的原因。递归Recursion两种解法都依赖递归遍历来计算各子树的高度/深度时间复杂度天然为 $O(N)$。树高 vs 树深Tree Height vs Depth高度是「从当前节点向下到叶子」的最长路径长度深度是「从根到当前节点」的路径长度。二者方向相反原文档特意将两种解法分拆就是为了对比这两个视角。问题定义与核心洞察N 叉树的直径定义为树中任意两个节点之间最长路径的边数节点数减一。核心洞察可以概括为一句话任意一条最长路径必然存在一个「最高点」最靠近根的节点路径从该点向下经过它的两个不同子分支分别到达两个叶子。因此经过某个节点的最长路径长度 该节点所有子节点中最大的两个高度之和。只要自底向上递归地求出每个子树的高度并在每个节点处用「前两大高度之和」更新全局最大值遍历结束后全局最大值就是答案。这也正是本仓库 hints/binary-tree-diameter.md 中针对 543 题给出的提示思路For any given node, the longest path that passes through it is the sum of the height of its left subtree and the height of its right subtree在 N 叉树上推广为「取前两大子树高度」。解法一基于高度的解法Distance with Height节点高度定义为从该节点向下到叶子的最长路径长度。直觉树的直径是任意两节点间的最长路径。这条路径必然以某个节点作为最高点在该点向下分叉进入两个不同子树。于是「经过任意节点的最长路径 其子节点中前两大高度之和」。递归计算高度并沿途追踪最大路径长度即得直径。算法步骤定义递归函数返回某节点的高度到其最深叶子后代的最长路径。叶子节点无子节点返回高度0。对每个节点遍历其子节点维护前两大高度max_height_1、max_height_2。每处理完一个子节点就用当前的前两大高度之和更新全局最大直径。返回max_height_1即本节点高度 最矮分支深度 1 的等价表达实现中用子树高度 1 累积。遍历整棵树后返回记录到的最大直径。多语言实现完整继承原文档Python—— 用闭包变量diameter携带全局最优值避免使用成员变量class Solution: def diameter(self, root: Node) - int: diameter 0 def height(node): return the height of the node nonlocal diameter if len(node.children) 0: return 0 # select the top two heights max_height_1, max_height_2 0, 0 for child in node.children: parent_height height(child) 1 if parent_height max_height_1: max_height_1, max_height_2 parent_height, max_height_1 elif parent_height max_height_2: max_height_2 parent_height # calculate the distance between the two farthest leaves nodes. distance max_height_1 max_height_2 diameter max(diameter, distance) return max_height_1 height(root) return diameterJava—— 全局最优值用成员字段diameter保存递归函数height负责更新class Solution { protected int diameter 0; /** * return the height of the node */ protected int height(Node node) { if (node.children.size() 0) return 0; // select the top two largest heights int maxHeight1 0, maxHeight2 0; for (Node child : node.children) { int parentHeight height(child) 1; if (parentHeight maxHeight1) { maxHeight2 maxHeight1; maxHeight1 parentHeight; } else if (parentHeight maxHeight2) { maxHeight2 parentHeight; } // calculate the distance between the two farthest leaves nodes. int distance maxHeight1 maxHeight2; this.diameter Math.max(this.diameter, distance); } return maxHeight1; } public int diameter(Node root) { this.diameter 0; height(root); return diameter; } }C—— 与 Java 结构一致用protected成员保存中间状态class Solution { protected: int dia 0; int height(Node* node) { if (node-children.size() 0) return 0; int maxHeight1 0, maxHeight2 0; for (Node* child : node-children) { int parentHeight height(child) 1; if (parentHeight maxHeight1) { maxHeight2 maxHeight1; maxHeight1 parentHeight; } else if (parentHeight maxHeight2) { maxHeight2 parentHeight; } int distance maxHeight1 maxHeight2; dia max(dia, distance); } return maxHeight1; } public: int diameter(Node* root) { dia 0; height(root); return dia; } };JavaScript—— 闭包捕获diameter箭头函数递归class Solution { /** * param {_Node} root * return {number} */ diameter(root) { let diameter 0; const height (node) { if (node.children.length 0) return 0; let maxHeight1 0, maxHeight2 0; for (const child of node.children) { const parentHeight height(child) 1; if (parentHeight maxHeight1) { maxHeight2 maxHeight1; maxHeight1 parentHeight; } else if (parentHeight maxHeight2) { maxHeight2 parentHeight; } const distance maxHeight1 maxHeight2; diameter Math.max(diameter, distance); } return maxHeight1; }; height(root); return diameter; } }C#public class Solution { private int diameter 0; private int Height(Node node) { if (node.children.Count 0) return 0; int maxHeight1 0, maxHeight2 0; foreach (Node child in node.children) { int parentHeight Height(child) 1; if (parentHeight maxHeight1) { maxHeight2 maxHeight1; maxHeight1 parentHeight; } else if (parentHeight maxHeight2) { maxHeight2 parentHeight; } int distance maxHeight1 maxHeight2; diameter Math.Max(diameter, distance); } return maxHeight1; } public int Diameter(Node root) { diameter 0; Height(root); return diameter; } }Go—— 自引用匿名函数实现递归闭包注意var height func(node *Node) int必须先声明再赋值func diameter(root *Node) int { dia : 0 var height func(node *Node) int height func(node *Node) int { if len(node.Children) 0 { return 0 } maxHeight1, maxHeight2 : 0, 0 for _, child : range node.Children { parentHeight : height(child) 1 if parentHeight maxHeight1 { maxHeight2 maxHeight1 maxHeight1 parentHeight } else if parentHeight maxHeight2 { maxHeight2 parentHeight } distance : maxHeight1 maxHeight2 if distance dia { dia distance } } return maxHeight1 } height(root) return dia }Kotlinclass Solution { private var diameter 0 private fun height(node: Node): Int { if (node.children.isEmpty()) return 0 var maxHeight1 0 var maxHeight2 0 for (child in node.children) { val parentHeight height(child) 1 if (parentHeight maxHeight1) { maxHeight2 maxHeight1 maxHeight1 parentHeight } else if (parentHeight maxHeight2) { maxHeight2 parentHeight } val distance maxHeight1 maxHeight2 diameter maxOf(diameter, distance) } return maxHeight1 } fun diameter(root: Node): Int { diameter 0 height(root) return diameter } }Swift—— 嵌套函数天然形成闭包var diameter被递归函数捕获class Solution { func diameter(_ root: Node) - Int { var diameter 0 func height(_ node: Node) - Int { if node.children.isEmpty { return 0 } var maxHeight1 0, maxHeight2 0 for child in node.children { let parentHeight height(child) 1 if parentHeight maxHeight1 { maxHeight2 maxHeight1 maxHeight1 parentHeight } else if parentHeight maxHeight2 { maxHeight2 parentHeight } let distance maxHeight1 maxHeight2 diameter max(diameter, distance) } return maxHeight1 } height(root) return diameter } }Rust—— 所有权语义下全局最优值通过mut i32参数显式传递不能像 Python/Kotlin 那样隐式捕获可变闭包变量// Definition: struct Node { val: i32, children: VecNode } struct Solution; impl Solution { pub fn diameter(root: Node) - i32 { let mut diameter 0; fn height(node: Node, diameter: mut i32) - i32 { if node.children.is_empty() { return 0; } let (mut max_height1, mut max_height2) (0, 0); for child in node.children { let parent_height height(child, diameter) 1; if parent_height max_height1 { max_height2 max_height1; max_height1 parent_height; } else if parent_height max_height2 { max_height2 parent_height; } let distance max_height1 max_height2; *diameter (*diameter).max(distance); } max_height1 } height(root, mut diameter); diameter } }复杂度时间复杂度$O(N)$ —— 每个节点恰好被访问一次。空间复杂度$O(N)$ —— 递归调用栈在最坏情况下树退化为链达到 $O(N)$。其中 $N$ 为树的节点数。解法二基于深度的解法Distance with Depth节点深度定义为该节点到根节点的路径长度。直觉不追踪「向下的距离」高度而是追踪「距根的距离」深度。经过某节点的路径长度 其两个最深叶子路径的深度之和减去当前节点深度的两倍——因为「下到一个叶子、回到当前节点、再到另一个叶子」中当前节点以下的路径段被重复计了两次。算法步骤定义递归函数参数为节点及其当前深度返回其子树内叶子的最大深度。叶子节点直接返回当前深度curr_depth。遍历子节点维护前两大深度max_depth_1、max_depth_2。注意初始化差异max_depth_1 curr_depthmax_depth_2 0。这一步处理了「节点只有一个深子分支」的退化情况——第二个值兜底为当前深度保证distance不会低估单分支路径。经过该节点的直径候选值max_depth_1 max_depth_2 - 2 * curr_depth更新全局直径。向父调用返回max_depth_1本点子树的最深叶子深度。多语言实现完整继承原文档Pythonclass Solution: def diameter(self, root: Node) - int: diameter 0 def maxDepth(node, curr_depth): return the maximum depth of leaves nodes descending from the current node nonlocal diameter if len(node.children) 0: return curr_depth # select the top 2 depths from its children max_depth_1, max_depth_2 curr_depth, 0 for child in node.children: depth maxDepth(child, curr_depth1) if depth max_depth_1: max_depth_1, max_depth_2 depth, max_depth_1 elif depth max_depth_2: max_depth_2 depth # calculate the distance between the two farthest leaves nodes distance max_depth_1 max_depth_2 - 2 * curr_depth diameter max(diameter, distance) return max_depth_1 maxDepth(root, 0) return diameterJavaclass Solution { protected int diameter 0; /** * return the maximum depth of leaves nodes descending from the given node */ protected int maxDepth(Node node, int currDepth) { if (node.children.size() 0) return currDepth; // select the top two largest depths int maxDepth1 currDepth, maxDepth2 0; for (Node child : node.children) { int depth maxDepth(child, currDepth 1); if (depth maxDepth1) { maxDepth2 maxDepth1; maxDepth1 depth; } else if (depth maxDepth2) { maxDepth2 depth; } // calculate the distance between the two farthest leaves nodes. int distance maxDepth1 maxDepth2 - 2 * currDepth; this.diameter Math.max(this.diameter, distance); } return maxDepth1; } public int diameter(Node root) { this.diameter 0; maxDepth(root, 0); return diameter; } }Cclass Solution { protected: int diameter 0; /** * return the maximum depth of leaves nodes descending from the given node */ int maxDepth(Node* node, int currDepth) { if (node-children.size() 0) return currDepth; // select the top two largest depths int maxDepth1 currDepth, maxDepth2 0; for (Node* child : node-children) { int depth maxDepth(child, currDepth 1); if (depth maxDepth1) { maxDepth2 maxDepth1; maxDepth1 depth; } else if (depth maxDepth2) { maxDepth2 depth; } // calculate the distance between the two farthest leaves nodes. int distance maxDepth1 maxDepth2 - 2 * currDepth; this-diameter max(this-diameter, distance); } return maxDepth1; } public: int diameter(Node* root) { this-diameter 0; maxDepth(root, 0); return diameter; } };JavaScript—— 注意此解法在 JS 中把直径更新放在了for循环之外每次调用只算一次与解法一的写法略有差异但结果等价class Solution { /** * param {_Node} root * return {number} */ diameter(root) { let diameter 0; const maxDepth (node, curr_depth) { /* return the maximum depth of leaves nodes descending from the current node */ if (node.children.length 0) { return curr_depth; } // select the top 2 depths from its children let max_depth_1 curr_depth, max_depth_2 0; for (const child of node.children) { const depth maxDepth(child, curr_depth 1); if (depth max_depth_1) { max_depth_2 max_depth_1; max_depth_1 depth; } else if (depth max_depth_2) { max_depth_2 depth; } } // calculate the distance between the two farthest leaves nodes const distance max_depth_1 max_depth_2 - 2 * curr_depth; diameter Math.max(diameter, distance); return max_depth_1; }; maxDepth(root, 0); return diameter; } }C#public class Solution { private int diameter 0; private int MaxDepth(Node node, int currDepth) { if (node.children.Count 0) return currDepth; int maxDepth1 currDepth, maxDepth2 0; foreach (Node child in node.children) { int depth MaxDepth(child, currDepth 1); if (depth maxDepth1) { maxDepth2 maxDepth1; maxDepth1 depth; } else if (depth maxDepth2) { maxDepth2 depth; } int distance maxDepth1 maxDepth2 - 2 * currDepth; diameter Math.Max(diameter, distance); } return maxDepth1; } public int Diameter(Node root) { diameter 0; MaxDepth(root, 0); return diameter; } }Gofunc diameter(root *Node) int { dia : 0 var maxDepth func(node *Node, currDepth int) int maxDepth func(node *Node, currDepth int) int { if len(node.Children) 0 { return currDepth } maxDepth1, maxDepth2 : currDepth, 0 for _, child : range node.Children { depth : maxDepth(child, currDepth1) if depth maxDepth1 { maxDepth2 maxDepth1 maxDepth1 depth } else if depth maxDepth2 { maxDepth2 depth } distance : maxDepth1 maxDepth2 - 2*currDepth if distance dia { dia distance } } return maxDepth1 } maxDepth(root, 0) return dia }Kotlinclass Solution { private var diameter 0 private fun maxDepth(node: Node, currDepth: Int): Int { if (node.children.isEmpty()) return currDepth var maxDepth1 currDepth var maxDepth2 0 for (child in node.children) { val depth maxDepth(child, currDepth 1) if (depth maxDepth1) { maxDepth2 maxDepth1 maxDepth1 depth } else if (depth maxDepth2) { maxDepth2 depth } val distance maxDepth1 maxDepth2 - 2 * currDepth diameter maxOf(diameter, distance) } return maxDepth1 } fun diameter(root: Node): Int { diameter 0 maxDepth(root, 0) return diameter } }Swiftclass Solution { func diameter(_ root: Node) - Int { var diameter 0 func maxDepth(_ node: Node, _ currDepth: Int) - Int { if node.children.isEmpty { return currDepth } var maxDepth1 currDepth, maxDepth2 0 for child in node.children { let depth maxDepth(child, currDepth 1) if depth maxDepth1 { maxDepth2 maxDepth1 maxDepth1 depth } else if depth maxDepth2 { maxDepth2 depth } let distance maxDepth1 maxDepth2 - 2 * currDepth diameter max(diameter, distance) } return maxDepth1 } maxDepth(root, 0) return diameter } }Rust// Definition: struct Node { val: i32, children: VecNode } struct Solution; impl Solution { pub fn diameter(root: Node) - i32 { let mut diameter 0; fn max_depth(node: Node, curr_depth: i32, diameter: mut i32) - i32 { if node.children.is_empty() { return curr_depth; } let (mut max_depth1, mut max_depth2) (curr_depth, 0); for child in node.children { let depth max_depth(child, curr_depth 1, diameter); if depth max_depth1 { max_depth2 max_depth1; max_depth1 depth; } else if depth max_depth2 { max_depth2 depth; } let distance max_depth1 max_depth2 - 2 * curr_depth; *diameter (*diameter).max(distance); } max_depth1 } max_depth(root, 0, mut diameter); diameter } }复杂度时间复杂度$O(N)$空间复杂度$O(N)$ —— 递归栈深度每次调用还携带一个curr_depth参数不改变量级。两种解法对比维度高度法解法一深度法解法二递归返回值本节点到最深叶子的高度相对值本子树最深叶子的绝对深度递归参数仅节点节点 当前深度直径候选式max_height_1 max_height_2max_depth_1 max_depth_2 - 2 * curr_depth前两大初始值(0, 0)(curr_depth, 0)兜底单分支情形直观程度更简洁面试首选强调「绝对位置」视角便于理解 LCA 类推导两种解法数学上完全等价设某节点深度为 $d$第 $i$ 个子分支的最深叶子深度为 $d_i$则其相对高度为 $d_i - d$候选直径 $(d_i - d) (d_j - d) d_i d_j - 2d$正好是深度法的表达式。常见错误Common Pitfalls原文档总结了三个典型陷阱逐一附对照代码错误一只考虑经过根节点的路径直径不必然经过根最长路径可能完全位于某棵子树内部。必须在每个节点处更新全局最大直径而不是只在根处计算# Wrong: Only checking diameter at root level def diameter(root): heights [height(child) for child in root.children] heights.sort(reverseTrue) return heights[0] heights[1] if len(heights) 2 else 0 # Correct: Track max diameter across all nodes def diameter(root): max_diameter 0 def height(node): nonlocal max_diameter # ... update max_diameter at every node height(root) return max_diameter错误二混淆高度与深度的定义高度向下到叶返回的是「相对距离」深度距根是「绝对距离」通常以参数传入。混用二者会得到错误的路径长度# Using height: returns longest path DOWN from node def height(node): if not node.children: return 0 return 1 max(height(child) for child in node.children) # Using depth: distance FROM ROOT passed as parameter def maxDepth(node, curr_depth): if not node.children: return curr_depth # Returns absolute depth return max(maxDepth(child, curr_depth 1) for child in node.children)错误三只追踪单一最大高度计算经过某节点的直径必须用到「前两大」子树高度。只维护一个最大值会丢掉第二分支直接漏掉答案# Wrong: Only tracking one maximum max_height 0 for child in node.children: max_height max(max_height, height(child) 1) diameter max_height # Missing the second branch! # Correct: Track top two heights max_height_1, max_height_2 0, 0 for child in node.children: h height(child) 1 if h max_height_1: max_height_1, max_height_2 h, max_height_1 elif h max_height_2: max_height_2 h diameter max_height_1 max_height_2源码佐证N 叉树直径与二叉树直径的同一范式本仓库中 559 题本身没有独立的源码文件但同主题的 543「二叉树直径」在多种语言下都有完整实现它们是理解上述 N 叉树解法最好的「退化特例」对照。从源码结构看两者是同一套「一次 DFS返回高度 全局更新」范式Python 对照python/0543-diameter-of-binary-tree.pyclass Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) - int: res 0 def dfs(root): nonlocal res if not root: return 0 left dfs(root.left) right dfs(root.right) res max(res, left right) return 1 max(left, right) dfs(root) return res对照 559 高度法可以看到清晰的推广关系二叉树里「子节点集合」恰好只有left、right两个因此「前两大高度之和」直接写成left right无需维护 top-two 变量递归返回1 max(left, right)对应 N 叉树中的「最矮分支 1」。C 对照cpp/0543-diameter-of-binary-tree.cppclass Solution { public: int diameterOfBinaryTree(TreeNode* root) { int result 0; dfs(root, result); return result; } private: int dfs(TreeNode* root, int result) { if (root NULL) { return 0; } int left dfs(root-left, result); int right dfs(root-right, result); result max(result, left right); return 1 max(left, right); } };这里用引用参数int result传递全局最优值与 559 Rust 解法的mut i32参数手法一致——在无成员变量可用的场景下「按引用传出全局状态」是跨语言的通用技巧。文件头注释也标明了同样的复杂度结论Time: O(n) / Space: O(n)。Java 对照java/0543-diameter-of-binary-tree.java给出了另一种计数习惯空节点返回-1非空节点先对左右各1于是left right就是经过当前节点的边数class Solution { int result -1; public int diameterOfBinaryTree(TreeNode root) { dfs(root); return result; } private int dfs(TreeNode current) { if (current null) { return -1; } int left 1 dfs(current.left); int right 1 dfs(current.right); result Math.max(result, (left right)); return Math.max(left, right); } }这说明「空节点返回 0 还是 -1」是同一算法的两种偏移写法只要「高度递推」与「直径累加」两处偏移保持一致结果就正确。这正是上文「错误二混淆高度/深度定义」要防范的偏移一致性问题的现实例子。Go 对照go/0543-diameter-of-binary-tree.go则用了指针参数*int携带全局最大值并自定义了max辅助函数该实现基于 Go 1.20 之前的版本未使用标准库泛型max可作为环境兼容性的注意点func diameterOfBinaryTree(root *TreeNode) int { maxLength : 0 dfs(root, maxLength) return maxLength } func dfs(t *TreeNode, maxLength *int) int { if t nil { return 0 } left : dfs(t.Left, maxLength) right : dfs(t.Right, maxLength) *maxLength max(*maxLength, leftright) return max(left, right) 1 }而仓库中 hints/binary-tree-diameter.md 的提示链与 559 文档的推导完全同构先指出暴力逐节点算左右高度是 $O(N^2)$再引导「能否在计算树高的同一次遍历中顺便求出直径」最后落点在「用全局变量在遍历中更新最大直径」。可以推断掌握 543 的这组提示与实现后559 的全部代码改动只有两处把left/right两个分支替换为对children的循环以及把「两个值直接相加」升级为「维护 top-two」。延伸阅读围绕 N 叉树数据结构本仓库articles/目录还有几篇可直接衔接的主题文章构成完整的学习路径N 叉树后序遍历 —— 熟悉children结构的递归/迭代遍历克隆 N 叉树 —— N 叉树的深拷贝实现将 N 叉树编码为二叉树 —— N 叉与二叉表示之间的双向转换N 叉树的序列化与反序列化 —— 用字符串承载任意叉数的树查找 N 叉树的根节点 —— N 叉树上的图论技巧。二叉树侧的直径题解文章 articles/binary-tree-diameter.md 与本文的「源码佐证」一节相互呼应适合放在一起复习「高度 全局更新」这一通用 DFS 模式。小结直径 任意节点处「前两大子分支高度之和」的全局最大值一次后序遍历即可求解时间与空间均为 $O(N)$。高度法与深度法数学等价区别仅在返回值语义相对高度 vs 绝对深度与偏移处理实现时须保证两处偏移一致。三个高频陷阱只在根处更新、混用高度/深度、只维护单一最大值。543二叉树是该问题「children 恰好两个」的特例仓库中的 0543 多语言实现 与 hints/binary-tree-diameter.md 可作为退化对照帮助验证自己对 N 叉版本每行代码的理解。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考