0543.二叉树的直径
难度：🟢 简单
标签：树、深度优先搜索、二叉树、递归
链接：543. 二叉树的直径
题目描述
给定一棵二叉树，你需要计算它的直径长度。
一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
注意： 两结点之间的路径长度是以它们之间边的数目表示。
示例 : 给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
解题思路
核心思想
本题的核心是找到树中任意两个节点之间的最长路径。这条最长路径有一个关键特性：它必然会穿过某个节点，并且等于该节点的左子树深度与右子树深度之和。因此，问题就转化为：对于树中的每一个节点，计算其 左子树深度 + 右子树深度，并找出这个值的全局最大值。
思路选择
深度优先搜索 (DFS) 结合 后序遍历 是解决此问题的最优思路。我们可以定义一个递归函数，该函数在计算每个节点“深度”的同时，附带更新一个全局的“最大直径”变量。
返回值：递归函数返回当前节点的深度。
副作用：在计算深度的过程中，顺便计算穿过当前节点的直径，并更新全局最大值。
关键步骤
初始化：在主函数中定义一个变量
maxDiameter = 0，用于记录和更新全局的最大直径。定义辅助函数
getDepth(node)：这是一个后序遍历的递归函数。 a. 终止条件: 如果node为null，说明到达叶子节点的子节点，其深度为 0，返回 0。 b. 递归分解: 递归调用getDepth来获取左子树的深度leftDepth和右子树的深度rightDepth。 c. 更新最大直径: 计算穿过当前node的路径长度（即直径）为leftDepth + rightDepth。用这个值来更新全局变量maxDiameter。maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth)。 d. 返回当前深度: 当前节点node的深度是其左右子树深度的较大者加 1，即Math.max(leftDepth, rightDepth) + 1。这个返回值是给父节点使用的。启动与返回：从根节点开始调用
getDepth(root)。调用结束后，maxDiameter中存储的就是最终答案，返回即可。
代码实现
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var diameterOfBinaryTree = function (root) {
let maxDiameter = 0;
// 辅助函数，计算深度的同时更新最大直径
var getDepth = function (node) {
if (node === null) return 0;
let leftDepth = getDepth(node.left);
let rightDepth = getDepth(node.right);
// 更新全局最大直径
maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
// 返回当前节点的深度
return Math.max(leftDepth, rightDepth) + 1;
}
// 从根节点开始递归
getDepth(root);
return maxDiameter;
};
复杂度分析
时间复杂度：O(n) 其中 n 是树的节点总数。我们对树进行一次完整的深度优先遍历，每个节点仅访问一次。
空间复杂度：O(h) 其中 h 是树的高度。空间复杂度主要由递归调用栈的深度决定。
相关题目
总结
本题是后序遍历思想的绝佳应用。通过一次递归，巧妙地同时完成了两项任务：向上传递“深度”信息，并在“归”的过程中更新全局的“直径”信息。这种“一趟遍历，解决所有问题”的思路是优化树相关算法的常用技巧。