하나의 그룹이 두 갈래 정렬 트리인지 아닌지를 판단한 결과

2494 단어
예를 들어 수조[5,7,6,9,11,10,8]를 제시하여 두 갈래 정렬 트리의 후차 반복 결과를 판단한다. 즉, 두 갈래 정렬 트리를 그려서 그 후차 반복 결과가 이 수조와 같게 할 수 있는지,true로 되돌아갈 수 있다면false로 되돌아갈 수 없다.
코드:
int is_valid(int *data, int n){
    if(data==NULL)return 0;
    int left=1;
    int right=1;
    int i=0;
    int j;
    int root=data[n-1];
    while(data[i]<root){
        i++;
    }

    for(j=i+1;j1;j++){
        if(data[j]<root){
            return 0;
        }
    }

    if(i>0){
        left=is_valid(data, i);
    }

    if(j1){
        right=is_valid(data, j);
    }

    return (left && right);
}

아이디어:
수조의 마지막 수는 틀림없이 뿌리 노드일 것이다. 그러면 처음부터 두루 훑어보고 첫 번째 뿌리 노드보다 작고 뿌리 노드보다 큰 경계를 찾은 다음에 이 수에서 뿌리 노드 사이의 수를 계속 훑어본다. 만약에 뿌리 노드보다 작은 수가 존재한다면(이론적으로 경계점에서 뿌리 노드보다 뒤로 가기 전의 수는 모두 뿌리 노드보다 커야 한다. 왜냐하면 그들은 뿌리 노드의 오른쪽 나무에 있기 때문이다.)그럼 false로 돌아가.
그리고 귀속...
전재 대상:https://www.cnblogs.com/focus1987/p/3996109.html
Unity Wifi 통신사 전파 수준의 취득(Android)
Unity 프로그래머를 위한 합법적인 휴식 편집기

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage