프로그래머 코드 면접 안내서 질서수 그룹 생성 균형 검색 트리 - 자바 구현

질서수 그룹 생성 균형 검색 두 갈래 트리

제목 설명:

질서수 그룹sortArr를 지정합니다. 중복된 값이 없는 것으로 알고 있습니다. 이 질서수 그룹으로 균형 검색 두 갈래 트리를 생성합니다. 그리고 이 검색 두 갈래 트리에서 반복된 결과는sortArr와 일치합니다.

문제 난이도:

medium

제목 사고방식:

먼저 질서수 그룹의 중간 값, 즉 두 갈래 나무에 대응하는 두결점을 찾아 이 두 갈래 나무의 왼쪽 나무와 오른쪽 나무를 차례로 찾아라.

코드 구현:

public static Node generateBST(int[] sortArr) {
        if (sortArr == null) {
            return null;
        }
        return generate(sortArr, 0, sortArr.length - 1);
    }

    public static Node generate(int[] sortArr, int l, int r) {
        if (l > r) {
            return null;
        }
        int mid = (l + r) / 2;
        Node head = new Node(sortArr[mid]);
        head.left = generate(sortArr, l, mid - 1);
        head.right = generate(sortArr, mid + 1, r);
        return head;
    }