Skip to main content

二叉树的直径

题目​

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

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

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

提示:
  • 树中节点数目在范围 [1, 10⁴] 内
  • -100 <= Node.val <= 100
示例

543-diameter-of-binary-tree

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

题解​

二叉树的直径可以理解为: 以某个节点为中心, 其左子树的最大深度加上右子树的最大深度. 因此, 我们需要遍历每个节点, 计算以该节点为中心的直径, 然后取所有直径中的最大值.

更具体地说, 对于任意一个节点 node:

计算其左子树的最大深度 leftDepth. 计算其右子树的最大深度 rightDepth. 以 node 为中心的直径为 leftDepth + rightDepth.

/**
 * 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 maxDiameter = 0

  // 相当于第 104 题
  var maxDepth = function (node) {
    if (!node) return 0

    const leftDepth = maxDepth(node.left)
    const rightDepth = maxDepth(node.right)

    maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth) // 在计算深度的同时更新直径

    return Math.max(leftDepth, rightDepth) + 1
  }

  maxDepth(root)
  return maxDiameter
}