이 진 트 리 의 순서 정렬 을 검증 합 니 다.
#
. 9
/ \
3 2
/ \ / \
4 1 # 6
/ \ / \ / \
# # # # # #
예 를 들 어 위의 이 진 트 리 는 문자열
"9,3,4,#,#,1,#,#,2,#,6,#,#"
로 서열 화 될 수 있 는데 그 중에서 #
은 빈 노드 를 대표 한다.쉼표 로 구 분 된 시퀀스 를 지정 하여 올 바른 이 진 트 리 의 순서 화 여 부 를 검증 합 니 다.트 리 를 재 구성 하지 않 는 조건 에서 실행 가능 한 알고리즘 을 만 듭 니 다.
쉼표 로 구 분 된 문자 나 정수 또는 표시
null
포인터 '#'
.입력 형식 은 항상 유효 하 다 고 생각 할 수 있 습 니 다. 예 를 들 어 두 개의 연속 적 인 쉼표 를 포함 하지 않 습 니 다. 예 를 들 어
"1,,3"
.예시 1:
: "9,3,4,#,#,1,#,#,2,#,6,#,#"
: true
예시 2:
: "1,#"
: false
예시 3:
: "9,#,#,1"
: false
제목 분석:
주어진 직렬 화 문자열 은 앞 순서에 따라 옮 겨 다 니 는 완전 이 진 트 리 입 니 다. 터미널 노드 는 '\ #' 로 대체 되 기 때문에 모든 노드 의 도 (터미널 노드 제외) 는 2 여야 합 니 다.
코드 구현:
public boolean isValidSerialization(String preorder)
{
String[] str = preorder.split(",");
int dif = 1;
for (String s : str)
{
if (--dif < 0)
return false;
if (!s.equals("#"))
dif += 2;
}
return dif == 0;
}
주 함수:
public static void main(String[] args)
{
T10 t = new T10();
Boolean b1 = t.isValidSerialization("9,3,4,#,#,1,#,#,2,#,6,#,#");
Boolean b2 = t.isValidSerialization("1,#,#");
Boolean b3 = t.isValidSerialization("9,#,#,1");
System.out.println(b1);
System.out.println(b2);
System.out.println(b3);
}
실행 결과:
true true false
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.