力扣 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; // 空节点的深度为0int 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;}
};