力扣 Hot 100 刷题记录 - 二叉树的直径

力扣 Hot 100 刷题记录 - 二叉树的直径

题目描述

二叉树的直径 是力扣 Hot 100 中的一道经典题目，题目要求如下：

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

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

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

解题思路

二叉树的直径本质上是 树中某两个节点之间的最长路径，而这条路径的长度等于 左子树的最大深度 + 右子树的最大深度。
关键点在于：

• 每个节点的直径候选值为其左子树深度 + 右子树深度。
• 最终答案为所有节点直径候选值的最大值。

递归法

1. 递归计算每个节点的左子树深度和右子树深度。
2. 在递归过程中，动态更新全局最大直径。
3. 递归函数的返回值是当前节点的深度（即左右子树深度的最大值 + 1）。

C++ 代码实现

/**
 * 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 {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        maxDepth(root); // 递归计算深度并更新最大直径
        return max_diameter;
    }

private:
    int max_diameter = 0; // 全局变量记录最大直径

    int maxDepth(TreeNode* root) {
        if (!root) return 0; // 空节点的深度为0

        int left_depth = maxDepth(root->left);   // 左子树深度
        int right_depth = maxDepth(root->right); // 右子树深度

        // 更新最大直径：左子树深度 + 右子树深度
        max_diameter = max(max_diameter, left_depth + right_depth);

        // 返回当前节点的深度（左右子树深度的最大值 + 1）
        return max(left_depth, right_depth) + 1;
    }
};