이 진 트 리 의 순서 정렬 을 검증 합 니 다.

이 진 트 리 를 직렬 화 하 는 방법 은 앞 순 서 를 사용 하여 옮 겨 다 니 는 것 이다.우리 가 비 어 있 는 노드 를 만 났 을 때, 우 리 는 이 노드 의 값 을 기록 할 수 있다.만약 그것 이 빈 노드 라면 우 리 는 표시 값 기록 을 사용 할 수 있 습 니 다. 예 를 들 어 #.
      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

좋은 웹페이지 즐겨찾기