03、二叉树的直径

厨子大约 5 分钟数据结构算法算法基地面试递归二叉树刷题程序厨校招社招

哈喽，大家好，我是厨子，今天给大家分享一道题目，二叉树的直径

https://leetcode.cn/problems/diameter-of-binary-tree/description/open in new window

题目描述

给定一棵二叉树，你需要计算它的直径长度。

一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

注意： 两结点之间的路径长度是以它们之间边的数目表示。

示例 1:

输入: root = [1,2,3,4,5]
输出: 3
          1
         / \
        2   3
       / \
      4   5

解释: 该树的直径是路径 4→2→1→3 或 5→2→1→3 的长度
路径长度 = 3（3条边）

示例 2:

输入: root = [1,2]
输出: 1
    1
   /
  2

解释: 路径 2→1，长度为 1（1条边）

约束条件:

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

其实通过题意，大家大致知道，什么是二叉树的直径啦，这里再详细介绍一下

什么是二叉树的直径？

直径的定义

二叉树的直径是任意两个节点之间最长路径上的边数。

关键理解：

路径可以不经过根节点
计算的是边数，不是节点数
需要找所有可能路径中的最长路径

示例：
          1
         / \
        2   3
       / \
      4   5

所有可能的路径：
- 4→2: 边数 = 1
- 5→2: 边数 = 1
- 2→1: 边数 = 1
- 3→1: 边数 = 1
- 4→2→1: 边数 = 2
- 5→2→1: 边数 = 2
- 4→2→5: 边数 = 2
- 4→2→1→3: 边数 = 3 ← 最长路径
- 5→2→1→3: 边数 = 3 ← 最长路径

直径 = 3

边数 vs 节点数

路径: 4 → 2 → 1 → 3

节点数 = 4（4个节点）
边数 = 3（3条边）

直径 = 边数 = 节点数 - 1

重要：题目要求的是边数！

直径的递归性质

对于任意节点，经过该节点的最长路径 = 左子树高度 + 右子树高度，其实悟懂这里，这个题目基本就能搞定了

          1
         / \
        2   3
       / \
      4   5

以节点1为中心的路径：
- 左子树高度 = 2（路径1→2→4或1→2→5）
- 右子树高度 = 1（路径1→3）
- 经过节点1的最长路径 = 2 + 1 = 3

以节点2为中心的路径：
- 左子树高度 = 1（路径2→4）
- 右子树高度 = 1（路径2→5）
- 经过节点2的最长路径 = 1 + 1 = 2

直径 = max(3, 2, ...) = 3

常见误区

误区1: 认为直径一定经过根节点
          1
         /
        2
       / \
      3   4
     /
    5

错误: 直径是 1→2（边数1）✗
正确: 直径是 5→3→2→4（边数3）✓
      这条路径不经过根节点1


误区2: 混淆边数和节点数
路径: 1 → 2 → 3

错误: 直径 = 3（节点数）✗
正确: 直径 = 2（边数）✓


误区3: 只考虑左右子树的高度
          1
         / \
        2   3

错误: 直径 = max(左高度, 右高度) = max(1, 1) = 1 ✗
正确: 直径 = 左高度 + 右高度 = 1 + 1 = 2 ✓


误区4: 认为直径就是树的高度
          1
         / \
        2   3

树的高度 = 2（从根到叶子的最长路径节点数）
树的直径 = 2（任意两节点间的最长路径边数）
虽然数值相同，但概念不同！

下面给大家提供一个例子，进行详细介绍

示例: [1,2,3,4,5,null,6,7]

          1
         / \
        2   3
       / \   \
      4   5   6
     /
    7

分析每个节点为中心的路径：
━━━━━━━━━━━━━━━━━━━━━━━━━━
节点1: 左高3 + 右高2 = 5 ✓（最长）
       路径: 7→4→2→1→3→6

节点2: 左高2 + 右高1 = 3
       路径: 7→4→2→5

节点3: 左高0 + 右高1 = 1
       路径: 3→6

节点4: 左高1 + 右高0 = 1
       路径: 7→4

其他节点: 都是叶子，直径0

直径 = max(5, 3, 1, 1, 0, ...) = 5

解题思路

在计算树高度的同时，记录每个节点的"左高度+右高度"的最大值。

关键点：

对每个节点，计算其左右子树的高度
经过该节点的最长路径 = 左高度 + 右高度
在所有节点中找最大值

递归 + 全局变量 ⭐

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    int maxDiameter = 0;  // 全局变量记录最大直径

    // 计算树的高度，同时更新最大直径
    int height(TreeNode* node) {
        // 递归终止条件：空节点高度为0
        if (node == nullptr) {
            return 0;
        }

        // 递归计算左右子树的高度
        int leftHeight = height(node->left);
        int rightHeight = height(node->right);

        // 更新最大直径
        // 经过当前节点的最长路径 = 左高度 + 右高度
        maxDiameter = max(maxDiameter, leftHeight + rightHeight);

        // 返回当前节点的高度
        return max(leftHeight, rightHeight) + 1;
    }

public:
    int diameterOfBinaryTree(TreeNode* root) {
        height(root);
        return maxDiameter;
    }
};