商城网站建设分为几块厦门seo排名收费
LeetCode 热题 100_二叉树的直径(40_543)
- 题目描述:
- 输入输出样例:
- 题解:
- 解题思路:
- 思路一(递归):
- 代码实现
- 代码实现(思路一(递归)):
- 以思路一为例进行调试
题目描述:
给你一棵二叉树的根节点,返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
输入输出样例:
示例 1:
输入:root = [1,2,3,4,5]
输出:3
解释:3 ,取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2:
输入:root = [1,2]
输出:1
提示:
树中节点数目在范围 [1, 104] 内
-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)原题链接
欢迎大家和我沟通交流(✿◠‿◠)