( “树” : DFS) 543. 二叉树的直径 ——Leetcode每日一题
543. 二叉树的直径
给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意 :两结点之间的路径长度是以它们之间边的数目表示。
思路:DFS
注意: 任意两个节点之间的边数都可能是最大直径, 最大的直径不一定包括根节点!
最大值不一定包含根节点,但是一定经过某一个节点;
经过该节点 左右子树的最大高度之和 即为最大直径; 于是,可以使用 DFS,求每个节点左右子树的最大高度之和,取出最大值 maxdia
,即为结果:
- 定义一个全局变量
maxdia
,用来记录最大直径, 使用height(root)
遍历所有的节点,height(root)
的作用是:找出以root
为根节点的左右子树的最大高度; maxdia
取值为以经过root
为根节点的左右子树的最大高度之和 ,为left right
;- 以
root
为左子树或右子树的高度为Math.max(left, right) 1
, 返回给root
的父节点,; - 通过递归,找到
maxdia
的最大值.
代码:(Java、C )
Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private int maxdir = 0;
public int diameterOfBinaryTree(TreeNode root) {
if(root == null) return 0;
height(root);
return maxdir;
}
public int height(TreeNode root){
if(root == null) return 0;
int left = height(root.left);
int right = height(root.right);
maxdir = Math.max(maxdir, left right);
return 1 Math.max(left, right);
}
}
C
/**
* Definition for a binary tree node.
* 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 maxdia = 0;
int diameterOfBinaryTree(TreeNode* root) {
if(root == NULL) return 0;
height(root);
return maxdia;
}
int height(TreeNode* root){
if(root == NULL) return 0;
int left = height(root->left);
int right = height(root->right);
maxdia = max(maxdia, left right);
return 1 max(left, right);
}
};
运行结果:
复杂度分析:
- 时间复杂度: O ( n ) O(n) O(n),其中
n
为二叉树的节点数,即遍历一棵二叉树的时间复杂度,每个结点只被访问一次。 - 空间复杂度: O ( H e i g h t ) O(Height) O(Height),其中
Height
为二叉树的高度。由于递归函数在递归过程中需要为每一层递归函数分配栈空间,所以这里需要额外的空间且该空间取决于递归的深度,而递归的深度显然为二叉树的高度,并且每次递归调用的函数里又只用了常数个变量,所以所需空间复杂度为 O ( H e i g h t ) O(Height) O(Height)。
题目来源:力扣。
放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!
注: 如有不足,欢迎指正!
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgfegab
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01