LeetCode 543 二叉树的直径

二叉树的直径：树中任意两个节点间最长路径的长度。这个路径可能经过根节点，也可能不经过。

算法思路

采用深度优先搜索(DFS)的后序遍历方式，计算每个节点的左右子树高度，并在过程中更新最大直径。

代码解析

var diameterOfBinaryTree = function(root) {let ans = 0  // 用于记录当前找到的最大直径const dfs = (node) => {if (node === null) {return 0  // 空节点的高度为0}// 递归计算左右子树的高度const lLen = dfs(node.left)const rLen = dfs(node.right)// 更新最大直径：当前节点作为"转折点"时的路径长度ans = Math.max(ans, lLen + rLen)// 返回当前节点的高度（左右子树中较高的那个 + 1）return Math.max(lLen, rLen) + 1}dfs(root)  // 从根节点开始遍历return ans
};

关键点解释

1. 后序遍历：先处理左右子树，再处理当前节点，这确保了在计算当前节点时，其子树的信息已经计算完成。

2. 高度计算：对于每个节点，我们计算其左右子树的高度：

   • lLen 是左子树的高度
   • rLen 是右子树的高度

3. 直径更新：直径是通过某个节点的最长路径，这个路径长度等于左子树高度 + 右子树高度。我们不断用这个值更新全局最大值 ans。

4. 返回值：每个节点返回的是以它为根的子树的高度，这是为了父节点能够计算它自己的直径。

示例分析

考虑以下二叉树：

      1/ \2   3/ \     4   5    

计算过程：

1. 节点4：lLen=0, rLen=0 → ans=0, 返回1
2. 节点5：lLen=0, rLen=0 → ans=0, 返回1
3. 节点2：lLen=1(来自4), rLen=1(来自5) → ans=2, 返回2
4. 节点3：lLen=0, rLen=0 → ans=2, 返回1
5. 节点1：lLen=2(来自2), rLen=1(来自3) → ans=3, 返回3

最终直径为3（路径[4,2,1,3]或[5,2,1,3]的长度）

时间复杂度

• 时间复杂度：O(n)，其中n是树中的节点数。每个节点只被访问一次。
• 空间复杂度：O(h)，其中h是树的高度。这是递归调用栈的空间消耗。