leetcode 543 二叉树的直径
程序员文章站
2022-03-03 10:35:11
...
给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
示例 :
给定二叉树
1 / \ 2 3 / \ 4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意:两结点之间的路径长度是以它们之间边的数目表示。
仔细观察例子中的那两个最长路径[4,2,1,3] 和 [5,2,1,3],我们转换一种角度来看,是不是其实就是根结点1的左右两个子树的深度之和再加1呢。那么我们只要对每一个结点求出其左右子树深度之和,再加上1就可以更新结果res了。
class Solution {
private int res = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxDepth(root);
return res;
}
private int maxDepth(TreeNode root){
if(root == null) return 0;
int left = maxDepth(root.left);
int right = maxDepth(root.right);
res = Math.max(res, left + right);
return Math.max(left, right) + 1;
}
}
上一篇: LeetCode 543. 二叉树的直径
下一篇: leetcode543-二叉树的直径
推荐阅读
-
leetcode 113 剑指offer 面试题34. 二叉树中和为某一值的路径(python3)
-
LeetCode第958题 二叉树的完全性检验
-
Leetcode刷题记录——958. 二叉树的完全性检验
-
leetcode 第 958 题:二叉树的完全性检验(C++)
-
leetcode 958 二叉树的完全性检验(超简洁写法)
-
leetcode 958. 二叉树的完全性检验(输出是否是完全二叉树 dfs/bfs每次假如队列的时候判断 值是不是sz)
-
Java实现 LeetCode 637 二叉树的层平均值(遍历树)
-
LeetCode637. 二叉树的层平均值(层序遍历)
-
【树】leetcode_637_二叉树的层平均值
-
leetCode 637 二叉树的层平均值(树,层次遍历)