LeetCode-热题100：543. 二叉树的直径

LeetCode-热题100：543. 二叉树的直径

引用

CSDN

1.

https://blog.csdn.net/qq_44852180/article/details/137826849

二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点。在LeetCode的这道题目中，我们需要计算给定二叉树的直径。

题目描述

给你一棵二叉树的根节点，返回该树的直径。
二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点
root
。
两节点之间路径的长度由它们之间边数表示。
示例 1：

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

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

代码及注释

  
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func diameterOfBinaryTree(root *TreeNode) int {
    // 定义一个内部的 dfs 函数用于深度优先搜索
    var dfs func(*TreeNode) int
    // 初始化最大直径为 0
    res := 0
    dfs = func(node *TreeNode) int {
        // 如果节点为空，返回 0
        if node == nil {
            return 0
        }
        // 递归计算左子树和右子树的深度
        l := dfs(node.Left)
        r := dfs(node.Right)
        // 更新最大直径
        res = max(res, l + r)
        // 返回当前节点的深度
        return max(l, r) + 1
    }
    // 调用 dfs 函数，开始计算
    dfs(root)
    return res
}
// 辅助函数，返回两个整数的最大值
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
  

代码解释

1. 定义
   dfs
   函数：
   dfs
   函数用于深度优先搜索二叉树，并在递归过程中更新最大直径。
2. 递归计算深度：

• 如果节点为空，则返回 0。
• 递归计算左子树
  l
  和右子树
  r
  的深度。
• 更新当前直径的最大值
  res
  为
  l + r
  。
• 返回当前节点的深度
  max(l, r) + 1
  。

3. 返回结果：最后返回最大直径
   res
   。
   路径为节点
   4
   、节点
   2
   、节点
   1
   、节点
   3
   或节点
   5
   。