TNotes.leetcode

Appearance

0543. 二叉树的直径【简单】

0543. 二叉树的直径【简单】 ​

1. 📝 题目描述 ​

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

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

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

示例 1：

img

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

示例 2：

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

提示：

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

2. 🎯 s.1 - 递归深度优先搜索 - 计算各节点深度 ​

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

  // 计算以当前节点为根的子树的最大深度
  function depth(node) {
    if (!node) return 0

    // 递归计算左右子树的深度
    let leftDepth = depth(node.left)
    let rightDepth = depth(node.right)

    // 更新直径：经过当前节点的路径长度 = 左子树深度 + 右子树深度
    diameter = Math.max(diameter, leftDepth + rightDepth)

    // 返回当前节点为根的子树的最大深度
    return Math.max(leftDepth, rightDepth) + 1
  }

  depth(root)
  return diameter
}
  • 时间复杂度：O(n)，其中 n 是二叉树的节点数，需要遍历每个节点一次
  • 空间复杂度：O(h)，其中 h 是二叉树的高度，递归调用栈的深度。平均情况下为 O(log⁡n)，最坏情况下为 O(n)
  • 算法思路：
    1. 深度优先搜索：
      • 使用递归函数 depth 计算每个节点为根的子树的最大深度
      • 同时在递归过程中计算经过每个节点的最长路径
    2. 直径计算：
      • 对于每个节点，经过该节点的最长路径长度等于左子树最大深度加上右子树最大深度
      • 使用全局变量 diameter 记录遇到的最大直径
    3. 深度返回：
      • 函数返回当前节点为根的子树的最大深度：Math.max(leftDepth, rightDepth) + 1

Discussions