543.二叉树的直径

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

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

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

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

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

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

解题思路

  • 定义DFS函数: 该函数接受一个节点作为参数，返回该节点为根的子树的最大深度，并同时更新全局变量 maxDiameter 来记录目前为止找到的最大直径。
  • 递归计算子树深度: 对于每个节点，递归计算其左子树和右子树的最大深度 leftDepth 和 rightDepth。
  • 更新直径: 当前节点的左右子树深度之和 leftDepth + rightDepth 表示经过该节点的最长路径的长度，将其与 maxDiameter 比较并更新 maxDiameter。
  • 返回最大深度: 函数返回 1 + max(leftDepth, rightDepth)，表示以当前节点为根的子树的最大深度。
func diameterOfBinaryTree(root *TreeNode) int {
      var maxDiameter int
      var dfs func(node *TreeNode) int
      dfs = func(node *TreeNode) int {
         if node == nil {
             return 0
         }
      
         leftDepth := dfs(node.Left)
         rightDepth := dfs(node.Right)
         if leftDepth + rightDepth > maxDiameter {
             maxDiameter = leftDepth + rightDepth
         }
      
         return 1 + max(leftDepth, rightDepth)	
      }
      dfs(root)
      return maxDiameter
}

  func max(a, b int) int {
      if a > b {
          return a
      }
      return b
  }