18923 二叉树的直径
时间: 2023-11-14 18:18:49 浏览: 43
二叉树的直径是指任意两个节点间最长路径的长度。可以使用递归的思想来解决这个问题,具体的做法是:
1. 对于当前节点,计算经过该节点的最长路径长度,即左子树高度+右子树高度。
2. 分别递归左右子树,得到左右子树的最长路径长度。
3. 取三者中的最大值作为当前节点的最长路径长度。
4. 递归处理所有节点,计算出直径。
下面是基于上述思路的 C++ 代码实现:
```c++
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
int diameterOfBinaryTree(TreeNode* root) {
if (!root) return 0;
int lHeight = height(root->left);
int rHeight = height(root->right);
int lDiameter = diameterOfBinaryTree(root->left);
int rDiameter = diameterOfBinaryTree(root->right);
return max(lHeight + rHeight, max(lDiameter, rDiameter));
}
int height(TreeNode* node) {
if (!node) return 0;
return 1 + max(height(node->left), height(node->right));
}
```
其中,diameterOfBinaryTree 函数用于计算二叉树的直径,height 函数用于计算二叉树的高度。