leetcode543-二叉树的直径

leetcode 543

思路

1. 路径长度计算：任意两个节点之间的路径长度，等于它们的最低公共祖先到它们各自的深度之和
2. 递归遍历：通过后序遍历（左右根）计算每个节点的左右子树深度，并更新全局最大直径
3. 深度与直径的关系：节点的深度是其左右子树深度的最大值加 1，而直径是左右子树深度之和

实现

const diameterOfBinaryTree = function (root) {let maxDepth = 0 // 全局最大直径// 递归计算每个节点的深度，并更新最大直径const deep = (root) => {if (!root) return 0; // 空节点深度为0// 计算左子树深度const leftLen = deep(root.left);// 计算右子树深度const rightLen = deep(root.right);// 当前节点的直径（经过该节点的最长路径）const curLen = leftLen + rightLen;// 更新全局最大直径maxDepth = Math.max(curLen, maxDepth);// 返回当前节点的深度（用于父节点计算）return Math.max(leftLen, rightLen) + 1}deep(root)return maxDepth;
}