543.二叉树的直径

二叉树的直径

给你一棵二叉树的根节点，返回该树的 直径。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度。这条路径可能经过也可能不经过根节点 root。

两节点之间路径的 长度 由它们之间边数表示。

示例 1：

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

示例 2：

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

提示：

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

解析

每个节点的直径 = 左子树深度 + 右子树深度，在计算深度的过程中更新最大直径。

/**
 * @param {TreeNode} root
 * @return {number}
 */
var diameterOfBinaryTree = function (root) {
  let maxDiameter = 0;

  function depth(node) {
    if (!node) return 0;
    const left = depth(node.left);
    const right = depth(node.right);
    maxDiameter = Math.max(maxDiameter, left + right);
    return Math.max(left, right) + 1;
  }

  depth(root);
  return maxDiameter;
};

一次 DFS 即可求解，时间复杂度 O(n)。