문제요약:
Given the root of a binary tree, return the length of the "diameter" of the tree.
"diameter" of a tree is the length of the longest path between any two nodes in a tree.
The path may or may not pass through the root.
제약:
number of nodes in range [1, 10^4]
-100 <= Node value <= 100
| 예제 1 입력. | 예제 1 출력. |
| [1,2,3,4,5] | 3 |
| 예제 2 입력. | 예제 2 출력. |
| [1,2] | 1 |
정답코드:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int diameter = 0;
int diameterOfBinaryTree(TreeNode* root) {
diameter = 0;
longestPath(root);
return diameter;
}
int longestPath(TreeNode* node){
if (node == NULL) return 0;
int leftPath = longestPath(node->left);
int rightPath = longestPath(node->right);
if ((leftPath + rightPath) > diameter)
{
diameter = (leftPath + rightPath);
}
return (leftPath >= rightPath) ? (leftPath + 1) : (rightPath + 1);
}
};
|
cs |
핵심 idea:
1. DFS 를 통해 모든 Node를 순회
2. 각각 Node를 순회 하는 동안
(left subtree의 longest path + right subtree의 longest path) 의 최대 값을 비교 후 업데이트.
원본 링크: https://leetcode.com/problems/diameter-of-binary-tree/
'알고리즘 문제풀이' 카테고리의 다른 글
| [알고리즘] LeetCode 1번 "Two Sum" (C/C++) - Don 임베디드 (0) | 2022.09.27 |
|---|---|
| [알고리즘] LeetCode 21번 "Merge Two Sorted Lists" (C/C++) - Don 임베디드 (0) | 2022.09.26 |
| [알고리즘] 백준 7568번 "덩치" (C/C++) - Don 임베디드 (23) | 2022.04.22 |
| [알고리즘] 백준 1181번 "단어 정렬" (C/C++) - Don 임베디드 (14) | 2022.04.21 |
| [알고리즘] 백준 18258번 "큐 2" (C/C++) - Don 임베디드 (11) | 2022.04.19 |
