LeetCode-543-二叉树的直径
# LeetCode-543-二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例1：
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
**注意：**两结点之间的路径长度是以它们之间边的数目表示。
# 解题思路
方法1、DFS：
- 二叉树的直径是不一定经过root节点的，可能存在于每个子树中，所以需要遍历每个节点的左右子树深度。动态记录最大的直径
- 直径 = max(左子树深度+右子树深度)
- 某节点子树的深度 = max(某节点左子树深度，某节点右子树深度)+1
# Java代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int res = 0;
public int diameterOfBinaryTree(TreeNode root) {
if(root==null) return 0;
calDepth(root);
return res;
}
public int calDepth(TreeNode root){
if(root==null) return 0;
int left = calDepth(root.left);
int right = calDepth(root.right);
res = Math.max(left+right,res);
return Math.max(left,right)+1;
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-08-07，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录