-
Notifications
You must be signed in to change notification settings - Fork 24
/
P49_1.java
40 lines (34 loc) · 1.29 KB
/
P49_1.java
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
35
36
37
38
39
40
package ch14;
import datatype.TreeNode;
public class P49_1 {
int result = 0;
public int dfs(TreeNode node) {
// 예외 처리 및 존재하지 않는 노드일 때 거리 0 리턴
if (node == null)
return 0;
// 왼쪽, 오른쪽의 각 리프 노드까지 재귀 DFS
int left = dfs(node.left);
int right = dfs(node.right);
// 현재 노드가 왼쪽 자식 노드와 동일한 경우 왼쪽 거리 1 증가
if (node.left != null && node.left.val == node.val)
left += 1;
else
// 다르면 거리를 0으로 초기화
left = 0;
// 현재 노드가 오른쪽 자식 노드와 동일한 경우 오른쪽 거리 1 증가
if (node.right != null && node.right.val == node.val)
right += 1;
else
// 다르면 거리를 0으로 초기화
right = 0;
// 왼쪽/오른쪽 자식 노드 간 거리의 합 최댓값이 최종 결과가 된다.
this.result = Math.max(this.result, left + right);
// 왼쪽/오른쪽 노드 중 큰 값을 리턴
return Math.max(left, right);
}
public int longestUnivaluePath(TreeNode root) {
// 재귀 DFS 시작
dfs(root);
return this.result;
}
}