# 543.Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longestpath between any two nodes in a tree. This path may or may not pass through the root.

Example: Given a binary tree

```          1
/ \
2   3
/ \
4   5    ```

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

## 解法一：

```public int diameterOfBinaryTree(TreeNode root) {
if (root==null) return 0;
return Math.max(depthTree(root.left)+depthTree(root.right),Math.max(diameterOfBinaryTree(root.left),diameterOfBinaryTree(root.right)));
}

public int depthTree(TreeNode root){
if (root == null) return 0;
return 1+Math.max(depthTree(root.right),depthTree(root.left));
}```

## 解法二：

```class Solution {
int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
getDiameter(root);
return max;
}

public int getDiameter(TreeNode root) {
if (root == null) return 0;
int left = getDiameter(root.left);
int right = getDiameter(root.right);
max = Math.max(max, left+right);
return Math.max(left, right) + 1;
}
}```

```public int getDiamter(TreeNode root){
if (root == null) return 0;
int left = getDiamter(root.left);
System.out.println(left);
int right = getDiamter(root.right);
System.out.println(right);
max = Math.max(max,left+right);
return Math.max(left,right)+1;
}```

```               5
//            / \
//           3   6
//          / \
//         2   4
/
1 ```

```0
0
1
0
2
0
0
1
3
0
0
1
4```

```         5
/ \
3   6
/ \
2   4
/ \
1  null
/  \
null null   0 0 1 0 2 0 0 1 3 0 0 1 4```

```    public int diameterOfBinaryTree(TreeNode root) {
int[] res = new int[1];
getDiamter(root,res);
return res[0];
}
public int getDiamter(TreeNode root,int[] res){
if (root == null) return 0;
int left = getDiamter(root.left,res);
int right = getDiamter(root.right,res);
res[0] = Math.max(res[0],left+right);
return Math.max(left,right)+1;
}```

0 条评论

## 相关文章

9410

### Java中Set集合是如何实现添加元素保证不重复的？

Java中Set集合是如何实现添加元素保证不重复的？ Set集合是一个无序的不可以重复的集合。今天来看一下为什么不可以重复。 Set是一个接口，最常用的实现类就...

40670

### [LeetCode] 39.Combination Sum

【原题】 Given a set of candidate numbers (C) (without duplicates) and a target ...

21870

24630

22920

### 【Java入门提高篇】Day26 Java容器类详解（八）HashSet源码分析

前面花了好几篇的篇幅把HashMap里里外外说了个遍，大家可能对于源码分析篇已经讳莫如深了。

11640

20340

### PHP数据结构（八） ——赫夫曼树实现字符串编解码(理论)

PHP数据结构（八）——赫夫曼树实现字符串编解码(理论) （原创内容，转载请注明来源，谢谢） 一、树和森林 1、树的三种存储结构 1)双亲表示法——数组下标、值...

42790

88320

### 基础算法

0.创建类 BinaryTreeNode 1.创建方法：传入根结点 2.判断根节点是否为空 3.判断左右结点是否同时为空 4.用self调用此方法，将根节点的左...

7410