🎈 作者：Linux猿
🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我，关注我，有问题私聊！
🎈 关注专栏：?数据结构和算法成神路【精讲】优质好文持续更新中……🚀🚀🚀
🎈 欢迎小伙伴们点赞👍、收藏?、留言💬
目录
🍓一、题目描述
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
注意：两结点之间的路径长度是以它们之间边的数目表示。
🍓二、测试样例
给定二叉树如下所示：
?返回 3, 上图中二叉树的直径是路径 [4, 2, 1, 3] 或者 [5, 2, 1, 3] ，两者长度均为 3。
🍓三、算法思路
首先，需要理解「二叉树直径」的含义，是指任意两个结点路径长度中的最大值。
遍历二叉树的每一个节点，统计当前节点的左右子树的最大长度 lNum 和 rNum，那么，当前节点的最大路劲长度为 lNum + rNum + 1，加 1 表示加上当前节点，遍历节点过程中记录最大值。
🍓四、代码实现
#include <iostream>
using namespace std;
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 calculatorDiameter(TreeNode* root, int& ans) {
if(!root) return 0;
//计算左子树最长
int lNum = calculatorDiameter(root->left, ans);
//计算右子树最长
int rNum = calculatorDiameter(root->right, ans);
//记录最优值
ans = max(ans, lNum + rNum + 1);
return max(lNum, rNum) + 1;
}
int diameterOfBinaryTree(TreeNode* root) {
int ans = 0;
calculatorDiameter(root, ans);
return ans - 1;
}
};
TreeNode* test() {
TreeNode* root = new(TreeNode);
root->val = 1;
TreeNode* p1 = new(TreeNode);
TreeNode* p2 = new(TreeNode);
root->left = p1;
root->right = p2;
TreeNode* p3 = new(TreeNode);
TreeNode* p4 = new(TreeNode);
p1->left = p3;
p1->right = p4;
p2->left = nullptr;
p2->right = nullptr;
p3->left = nullptr;
p3->right = nullptr;
p4->left = nullptr;
p4->right = nullptr;
return root;
}
int main()
{
TreeNode* root = test();
Solution obj;
cout<<obj.diameterOfBinaryTree(root)<<endl;
return 0;
}
🍓五、复杂度分析
🍅5.1 时间复杂度
时间复杂度：O(n)，其中，n 表示二叉树节点的个数，在上述算法中需要遍历二叉树的所有节点，所以时间复杂度为 O(n)。
🍅5.2 空间复杂度
空间复杂度：O(n)，其中，n 表示二叉树节点的个数，在上述算法中，空间复杂度主要在于递归过程中栈的深度，最深为单支的二叉树，所以空间复杂度为 O(n)。
🍓六、总结
本题主要理解二叉树直接的前提下，遍历每一个节点，并计算最大长度，取最大值即可，使用深度优先搜索比较方便。
🎈 感觉有帮助记得「一键三连」支持下哦！有问题可在评论区留言💬，感谢大家的一路支持！🤞猿哥将持续输出「优质文章」回馈大家！🤞🌹🌹🌹🌹🌹🌹🤞
