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

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

题目描述

二叉树的直径 是力扣 Hot 100 中的一道经典题目，题目要求如下：
给定一棵二叉树的根节点 root，返回这棵树的 直径。
二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径大概颠末根节点，也大概不颠末。
示例 1：
输入：root = [1,2,3,4,5]
输出：3
示例 2：
输入：root = [1,2]
输出：1

---

解题思绪

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

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

递归法

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

---

C++ 代码实现

1. /**
2. * Definition for a binary tree node.
3. * struct TreeNode {
4. *     int val;
5. *     TreeNode *left;
6. *     TreeNode *right;
7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10. * };
11. */
12. class Solution {
13. public:
14.     int diameterOfBinaryTree(TreeNode* root) {
15.         maxDepth(root); // 递归计算深度并更新最大直径
16.         return max_diameter;
17.     }
19. private:
20.     int max_diameter = 0; // 全局变量记录最大直径
22.     int maxDepth(TreeNode* root) {
23.         if (!root) return 0; // 空节点的深度为0
25.         int left_depth = maxDepth(root->left);   // 左子树深度
26.         int right_depth = maxDepth(root->right); // 右子树深度
28.         // 更新最大直径：左子树深度 + 右子树深度
29.         max_diameter = max(max_diameter, left_depth + right_depth);
31.         // 返回当前节点的深度（左右子树深度的最大值 + 1）
32.         return max(left_depth, right_depth) + 1;
33.     }
34. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。