二叉树的直径
七崽爱吃小饼干2026/01/29阅读 0
二叉树的直径
给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
示例 1：
codeType
输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2：
codeType
输入：root = [1,2]
输出：1
提示：
- 树中节点数目在范围 [1, 104] 内
- -100 <= Node.val <= 100
解法
ts
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function diameterOfBinaryTree(root: TreeNode | null): number {
// 左子树和右子树的深度之和的最大值
let res = 0
const helper = (node: TreeNode | null): number => {
if(!node) return 0
const L = helper(node.left) // 当前节点左子树的深度
const R = helper(node.right) // 当前节点右子树的深度
res = Math.max(res, L + R) // 维护最大直径 当前树的直径为左子树深度+右子树深度
return Math.max(L, R) + 1 // 大的一个 + 1为当前树的深度
}
helper(root)
return res
};