【LeetCode热题100道笔记】二叉树的直径

题目描述

给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。

示例 1：

输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

示例 2：
输入：root = [1,2]
输出：1

提示：
树中节点数目在范围 $[1,10^4]$ 内
-100 <= Node.val <= 100

思考一

思考一：基础递归（分治计算三类直径）

核心是分治思想：将二叉树直径拆解为“左子树内部直径”“右子树内部直径”“跨当前根节点的直径”三类，递归计算后取最大值。其中“跨根直径”需依赖子树深度（路径边数=左子树深度+右子树深度）。

算法过程

1. 终止条件：若当前节点为null（空树），直径为0，直接返回0。

2. 计算三类直径：

   • 左子树内部直径：递归调用diameterOfBinaryTree(root.left)，得到左子树自身的最长路径边数；
   • 右子树内部直径：递归调用diameterOfBinaryTree(root.right)，得到右子树自身的最长路径边数；
   • 跨当前根节点的直径：先通过maxDepth函数计算左子树深度（节点数）和右子树深度，路径边数=左深度+右深度（因深度是节点数，边数=节点数-1，左右深度相加时“-1”抵消，直接求和即可）；

3. 返回最大值：取三类直径中的最大值，作为当前树的直径。

4. 辅助函数maxDepth（计算子树深度）：

   • 终止条件：空节点深度为0；
   • 递归计算左、右子树深度，当前节点深度=max(左深度, 右深度)+1（包含当前节点）。

时空复杂度

• 时间复杂度：O(n²)，n为二叉树节点总数。
  原因：对于每个节点，diameterOfBinaryTree递归会触发maxDepth递归，而maxDepth对每个子树需遍历所有节点。最坏情况下（链状树），总操作次数为O(n²)。
• 空间复杂度：O(h)，h为二叉树高度。
  原因：递归调用栈深度取决于树高，平衡树h=O(log n)，链状树h=O(n)。

代码

/*** 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) {    if (!root) return 0;const maxLeft = diameterOfBinaryTree(root.left);const maxRight = diameterOfBinaryTree(root.right);const crossRoot = maxDepth(root.left) + maxDepth(root.right);return Math.max(maxLeft, maxRight, crossRoot);
};function maxDepth(root) {if (!root) return 0;return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

思考二：优化递归（后序遍历避免重复计算）

基础递归的问题是maxDepth重复遍历节点（如计算父节点直径时，会重复计算子节点的深度）。优化思路是后序遍历：在计算子树深度的同时，同步更新全局最大直径（跨当前节点的直径=左深度+右深度），实现“一次遍历，双重用途”。

算法过程

1. 初始化全局变量：定义ans存储最大直径，初始值为0（空树或单节点树的直径）。
2. 后序遍历DFS函数（计算深度+更新直径）：
   • 终止条件：若当前节点为null，深度为0，直接返回0；
   • 左子树处理：递归调用dfs(node.left)，得到左子树深度maxLeftDepth；
   • 右子树处理：递归调用dfs(node.right)，得到右子树深度maxRightDepth；
   • 更新最大直径：当前节点的跨根直径=左深度+右深度，若该值大于ans，则更新ans；
   • 返回当前节点深度：当前节点深度=max(左深度, 右深度)+1（包含当前节点）。
3. 触发遍历与返回结果：调用dfs(root)触发后序遍历，最终返回ans（全局最大直径）。

时空复杂度

• 时间复杂度：O(n)，n为二叉树节点总数。
  原因：后序遍历仅遍历每个节点一次，每个节点的操作（计算深度、更新直径）均为O(1)，总操作次数为O(n)，效率远高于基础递归。
• 空间复杂度：O(h)，h为二叉树高度。
  原因：递归调用栈深度取决于树高，平衡树h=O(log n)，链状树h=O(n)（与基础递归一致，但避免了重复计算，时间效率更优）。

代码

/*** 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) {    if (!root) return 0;let ans = 0;const dfs = function(node) {if (!node) return 0;let maxLeftDepth = dfs(node.left);let maxRightDepth = dfs(node.right);ans = Math.max(ans, maxLeftDepth + maxRightDepth);return Math.max(maxLeftDepth, maxRightDepth) + 1;};dfs(root);return ans;
};