力扣 Hot 100 刷题纪录 - 二叉树的直径
力扣 Hot 100 刷题纪录 - 二叉树的直径题目描述
二叉树的直径 是力扣 Hot 100 中的一道经典题目，题目要求如下：
给定一棵二叉树的根节点 root，返回这棵树的 直径。
二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径大概颠末根节点，也大概不颠末。
示例 1：
输入：root =
输出：3
示例 2：
输入：root =
输出：1
解题思绪
二叉树的直径本质上是 树中某两个节点之间的最长路径，而这条路径的长度即是 左子树的最大深度 + 右子树的最大深度。
关键点在于：
[*]每个节点的直径候选值为其左子树深度 + 右子树深度。
[*]最终答案为所有节点直径候选值的最大值。
递归法
[*]递归计算每个节点的左子树深度和右子树深度。
[*]在递归过程中，动态更新全局最大直径。
[*]递归函数的返回值是当前节点的深度（即左右子树深度的最大值 + 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;
}
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]