LeetCode高频考点二叉树直径问题的3种解法全解析Python/Java/C在算法面试中二叉树相关问题几乎占据了半壁江山。其中二叉树直径问题LeetCode 543因其考察递归思维和深度优先搜索DFS的变形应用成为高频面试题。本文将深入解析三种不同思路的解法并提供Python、Java、C三种语言的实现对比帮助你在面试中游刃有余。1. 理解二叉树直径问题二叉树直径定义为树中任意两个节点间最长路径的边数。这条路径可能穿过根节点也可能完全位于某个子树中。例如1 / \ 2 3 / \ 4 5这棵树的直径是3路径4-2-5或5-2-1-3。关键观察点直径长度 左子树深度 右子树深度需要全局变量记录最大值因为最长路径可能不经过当前节点边数 节点数 - 1注意LeetCode官方定义直径时使用边数而非节点数这与某些教材不同解题时需特别注意。2. 基础递归解法后序遍历这是最直观的解法通过后序遍历计算每个节点的左右子树深度同时更新全局最大直径。算法步骤递归计算左子树深度递归计算右子树深度当前节点直径 左深度 右深度更新全局最大值返回当前子树的最大深度max(左深, 右深) 1Python实现class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) - int: self.max_diameter 0 def depth(node): if not node: return 0 left depth(node.left) right depth(node.right) self.max_diameter max(self.max_diameter, left right) return max(left, right) 1 depth(root) return self.max_diameterJava实现class Solution { int maxDiameter 0; public int diameterOfBinaryTree(TreeNode root) { maxDepth(root); return maxDiameter; } private int maxDepth(TreeNode node) { if (node null) return 0; int left maxDepth(node.left); int right maxDepth(node.right); maxDiameter Math.max(maxDiameter, left right); return Math.max(left, right) 1; } }C实现class Solution { public: int diameterOfBinaryTree(TreeNode* root) { int maxDiameter 0; maxDepth(root, maxDiameter); return maxDiameter; } private: int maxDepth(TreeNode* node, int maxD) { if (!node) return 0; int left maxDepth(node-left, maxD); int right maxDepth(node-right, maxD); maxD max(maxD, left right); return max(left, right) 1; } };复杂度分析时间复杂度O(n)每个节点访问一次空间复杂度O(h)递归栈空间h为树高3. 非递归解法迭代后序遍历对于不喜欢递归或担心栈溢出的场景可以使用迭代法模拟后序遍历。关键是用栈保存节点和已访问状态。Python实现def diameterOfBinaryTree(root): if not root: return 0 max_diameter 0 stack [(root, False)] depth {None: 0} # 空节点深度为0 while stack: node, visited stack.pop() if visited: left depth[node.left] right depth[node.right] max_diameter max(max_diameter, left right) depth[node] max(left, right) 1 else: stack.append((node, True)) if node.right: stack.append((node.right, False)) if node.left: stack.append((node.left, False)) return max_diameterJava实现public int diameterOfBinaryTree(TreeNode root) { if (root null) return 0; int maxDiameter 0; DequePairTreeNode, Boolean stack new ArrayDeque(); MapTreeNode, Integer depth new HashMap(); depth.put(null, 0); stack.push(new Pair(root, false)); while (!stack.isEmpty()) { PairTreeNode, Boolean pair stack.pop(); TreeNode node pair.getKey(); boolean visited pair.getValue(); if (visited) { int left depth.get(node.left); int right depth.get(node.right); maxDiameter Math.max(maxDiameter, left right); depth.put(node, Math.max(left, right) 1); } else { stack.push(new Pair(node, true)); if (node.right ! null) stack.push(new Pair(node.right, false)); if (node.left ! null) stack.push(new Pair(node.left, false)); } } return maxDiameter; }优势对比方法优点缺点递归代码简洁易理解栈空间可能溢出迭代避免栈溢出需要额外存储访问状态4. 类成员变量解法面向对象风格对于习惯面向对象编程的开发者可以将最大直径作为类成员变量使代码结构更清晰。C实现class Solution { int maxDiameter; int depth(TreeNode* node) { if (!node) return 0; int left depth(node-left); int right depth(node-right); maxDiameter max(maxDiameter, left right); return max(left, right) 1; } public: int diameterOfBinaryTree(TreeNode* root) { maxDiameter 0; depth(root); return maxDiameter; } };Python类实现class Solution: def __init__(self): self.max_diameter 0 def diameterOfBinaryTree(self, root): def depth(node): if not node: return 0 left depth(node.left) right depth(node.right) self.max_diameter max(self.max_diameter, left right) return max(left, right) 1 depth(root) return self.max_diameter5. 相关题目扩展LeetCode 687最长同值路径二叉树直径问题的变种是LeetCode 687最长同值路径区别在于路径上的节点值必须相同。解法对比递归返回的不再是单纯的深度而是与当前节点值相同的最大深度更新全局最大值时需要检查节点值是否相同Python示例class Solution: def longestUnivaluePath(self, root): self.max_length 0 def dfs(node): if not node: return 0 left dfs(node.left) right dfs(node.right) left_path left 1 if node.left and node.left.val node.val else 0 right_path right 1 if node.right and node.right.val node.val else 0 self.max_length max(self.max_length, left_path right_path) return max(left_path, right_path) dfs(root) return self.max_length关键区别点需要比较节点值与子节点值路径可以不经过根节点返回值可能被重置为0当子节点值与当前节点不同时在实际面试中面试官可能会先问543题再扩展到687题来考察举一反三能力。掌握这两种问题的内在联系能展现你的算法思维深度。