543.Diameter_of_Binary_Tree

var diameterOfBinaryTree = function (root) {
  // 初始化最大直径为 0，用于在递归过程中记录全局最大值
  let ans = 0

  /**
   * 深度优先搜索（DFS）函数，用于计算以当前节点为根的子树的最大链长
   * 同时在递归过程中更新全局最大直径
   * @param {TreeNode} node - 当前遍历的节点
   * @returns {number} - 以当前节点为端点的最大链长（边数）
   */
  function dfs(node) {
    // 递归终止条件：如果节点为空，返回 -1
    // 为什么返回 -1？因为叶子节点的子节点为空，叶子节点到空节点的边数为 0
    // 叶子节点的左/右链长 = dfs(null) + 1 = -1 + 1 = 0，符合实际意义
    if (node === null) {
      return -1
    }

    // 递归计算左子树的最大链长（当前节点到左子树最深节点的边数）
    // +1 是因为要加上当前节点到左子节点的这条边
    const lLen = dfs(node.left) + 1

    // 递归计算右子树的最大链长（当前节点到右子树最深节点的边数）
    // +1 是因为要加上当前节点到右子节点的这条边
    const rLen = dfs(node.right) + 1

    // 关键逻辑：以当前节点为转折点的路径长度 = 左链长 + 右链长
    // 用这个值更新全局最大直径 ans
    ans = Math.max(ans, lLen + rLen)

    // 返回以当前节点为端点的最大链长（供父节点计算使用）
    // 父节点只能选择左/右中更长的一条链，所以返回两者的最大值
    return Math.max(lLen, rLen)
  }

  // 从根节点开始执行深度优先搜索
  dfs(root)

  // 返回最终计算出的二叉树直径
  return ans
}

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