LeetCode 热题 100_二叉树的直径（40_543_简单_C++）(二叉树；递归)

题目描述：

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

输入输出样例：

示例 1：

输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

示例 2：
输入：root = [1,2]
输出：1

提示：
树中节点数目在范围 [1, 10⁴] 内
-100 <= Node.val <= 100

题解：

解题思路：

思路一（递归）：

1、我们可以采用和计算二叉树深度同样的思想，计算二叉树的深度是挑选左右子树中深度的最大值，而二叉树的直径是左子树的最大深度深度+右子树的最大深度。
2、复杂度分析：
① 时间复杂度：O(N)，其中 N 为二叉树的节点数，即遍历一棵二叉树的时间复杂度，每个结点只被访问一次。
② 空间复杂度：O(h)，其中 h 为二叉树的高度（递归需要额外的栈空间）。
本题的力扣官方题解链接（非常不错）

代码实现

代码实现（思路一（递归））：

//二叉树的直径
int diameterOfBinaryTree(TreeNode* root) {depth(root);return ans;
}int depth(TreeNode *root){if(root==nullptr) return 0;//left：左子树的高度（高度指从叶结点开始测量）int left=depth(root->left);//right：右子树的高度int right=depth(root->right);//更新树的最大直径ans=max((left+right),ans);// 返回当前节点的深度return max(left,right)+1;
}

以思路一为例进行调试

#include<iostream>
#include<vector>
#include<queue>
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 Soluton
{int ans=0;//注意递归返回的是深度，所以我们要分成两个函数int depth(TreeNode *root){if(root==nullptr) return 0;//left：左孩子子树的高度（高度指从叶结点开始测量）int left=depth(root->left);//right：右孩子子树的高度int right=depth(root->right);//求当前两节点间的最大长度ans=max((left+right),ans);return max(left,right)+1;}public://二叉树的直径int diameterOfBinaryTree(TreeNode* root) {depth(root);return ans;}//通过数组创建二叉树（数组元素为-1代表nullptr）TreeNode *creatTree(vector<int> nums){if(nums.empty()) return nullptr;TreeNode *root=new TreeNode(nums[0]);queue<TreeNode *> q;q.push(root);int i=1;while (i<nums.size()){TreeNode *node=q.front();q.pop();if(i<nums.size()&&nums[i]!=-1){node->left=new TreeNode(nums[i]);q.push(node->left);}++i;if(i<nums.size()&&nums[i]!=-1){node->right=new TreeNode(nums[i]);q.push(node->right);}++i;}return root;}//中序遍历输出二叉树(用于调试二叉树创建是否正确)void inorder(TreeNode *root){if(root==nullptr) return ;inorder(root->left);cout<<root->val<<" ";inorder(root->right);} 
};int main(){vector<int> nums={1,2,3,4,5};Soluton s;//创建二叉树TreeNode *root=s.creatTree(nums);//调试二叉树是否创建正确//s.inorder(root); cout<<"二叉树的直径:"<<s.diameterOfBinaryTree(root);return 0;
}

LeetCode 热题 100_二叉树的直径（40_543)原题链接
欢迎大家和我沟通交流(✿◠‿◠)