树 --- leedcode 543 二叉树的直径 (Easy)
程序员文章站
2022-05-20 10:37:56
...
题目
给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点
路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意:两结点之间的路径长度是以它们之间边的数目表示。
解析
- 这题有坑:二叉树的最大直径不一定是经过根节点。
- 最大直径指 :每个节点的左右子树的高度和的最大值。
- 使用一个变量max来,来记录这个最大值。
java代码
class Solution {
private int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
if(root == null) {
return 0;
}
height(root);
return max;
}
private int height (TreeNode root) {
if(root == null) {
return 0;
}
int left = height(root.left);
int right = height(root.right);
// 取每个节点的直径值的最大值
max = Math.max(max, left+ right );
return Math.max( left,right) +1;
}
}
js代码
var diameterOfBinaryTree = function(root) {
let max = 0;
if(root == null) {
return 0;
}
height(root);
return max;
function height (root) {
if(root == null){
return 0;
}
let left = height(root.left) ;
let right = height(root.right);
// 取每个节点的直径值的最大值
max = Math.max(left+right, max);
return Math.max(left,right) + 1;
}
};
上一篇: java 递归删除指定文件夹下的所有内容
下一篇: pandas的数学计算操作