Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit4de91c1

Browse files
committed
feat: add 543
1 parent5aaebae commit4de91c1

File tree

7 files changed

+153
-154
lines changed

7 files changed

+153
-154
lines changed

‎README.md

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -50,6 +50,7 @@
5050
|119|[Pascal's Triangle II][119]|Array|
5151
|121|[Best Time to Buy and Sell Stock][121]|Array, Dynamic Programmin|
5252
|122|[Best Time to Buy and Sell Stock II][122]|Array, Greedy|
53+
|543|[Diameter of Binary Tree][543]|Tree|
5354

5455

5556
##Medium
@@ -108,10 +109,12 @@
108109
[119]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/119/README.md
109110
[121]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/121/README.md
110111
[122]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/122/README.md
112+
[543]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/543/README.md
111113

112114
[002]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/002/README.md
113115
[003]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/003/README.md
114116
[008]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/008/README.md
115117
[019]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/019/README.md
118+
[554]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/554/README.md
116119

117120
[004]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/004/README.md

‎note/543/README.md

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
#[Diameter of Binary Tree][title]
2+
3+
##Description
4+
5+
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**longest** path between any two nodes in a tree. This path may or may not pass through the root.
6+
7+
**Example:**
8+
Given a binary tree
9+
10+
```
11+
1
12+
/ \
13+
2 3
14+
/ \
15+
4 5
16+
17+
```
18+
19+
Return**3**, which is the length of the path[4,2,1,3] or[5,2,1,3].
20+
21+
**Note:** The length of path between two nodes is represented by the number of edges between them.
22+
23+
**Tags:** Tree
24+
25+
26+
##思路
27+
28+
题意是让你算出二叉树中最远的两个节点的距离，分别计算左右子树的最大高度，然后不断迭代出其和的最大值就是最终结果。
29+
30+
```java
31+
/**
32+
* Definition for a binary tree node.
33+
* public class TreeNode {
34+
* int val;
35+
* TreeNode left;
36+
* TreeNode right;
37+
* TreeNode(int x) { val = x; }
38+
* }
39+
*/
40+
classSolution {
41+
int max=0;
42+
43+
publicintdiameterOfBinaryTree(TreeNoderoot) {
44+
helper(root);
45+
return max;
46+
}
47+
48+
privateinthelper(TreeNoderoot) {
49+
if (root==null)return0;
50+
int l= helper(root.left);
51+
int r= helper(root.right);
52+
if (l+ r> max) max= l+ r;
53+
returnMath.max(l, r)+1;
54+
}
55+
}
56+
```
57+
58+
59+
##结语
60+
61+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我GitHub上的LeetCode题解：[awesome-java-leetcode][ajl]
62+
63+
64+
65+
[title]:https://leetcode.com/problems/diameter-of-binary-tree
66+
[ajl]:https://github.com/Blankj/awesome-java-leetcode

‎project/leetcode/.idea/workspace.xml

Lines changed: 50 additions & 154 deletions
Some generated files are not rendered by default. Learn more aboutcustomizing how changed files appear on GitHub.
Binary file not shown.
Binary file not shown.
Binary file not shown.
Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
packagecom.blankj.easy._543;
2+
3+
4+
importcom.blankj.structure.TreeNode;
5+
6+
/**
7+
* <pre>
8+
* author: Blankj
9+
* blog : http://blankj.com
10+
* time : 2017/10/13
11+
* desc :
12+
* </pre>
13+
*/
14+
publicclassSolution {
15+
intmax =0;
16+
17+
publicintdiameterOfBinaryTree(TreeNoderoot) {
18+
helper(root);
19+
returnmax;
20+
}
21+
22+
privateinthelper(TreeNoderoot) {
23+
if (root ==null)return0;
24+
intl =helper(root.left);
25+
intr =helper(root.right);
26+
if (l +r >max)max =l +r;
27+
returnMath.max(l,r) +1;
28+
}
29+
30+
publicstaticvoidmain(String[]args) {
31+
Solutionsolution =newSolution();
32+
System.out.println(solution.diameterOfBinaryTree(TreeNode.createTestData("[1,2,3,4,5]")));
33+
}
34+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp