刷题20:二叉树的直径
文章目录
Leetcode: 543. 二叉树的直径
要点:二叉树的直径就是左右子树和根节点构成的最长节点数量减一。设置一个中间变量max,每次寻找左右子树和根节点所构成的节点数量与max比较大小,较大的用max保存,直到最后所有左右子树和根节点构成的最长节点路径就是max,最后用max-1就是最大直径。该题的本质还是求树的深度。
class Solution {
int max = Integer.MIN_VALUE;
public int diameterOfBinaryTree(TreeNode root) {
depth(root);
return max - 1;
}
public int depth(TreeNode root){
if(root == null) return 0;
int l = depth(root.left);
int r = depth(root.right);
max = Math.max(max,l + r + 1);
return Math.max(l,r) + 1;
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论