면접 문제 7 - 두 갈래 나무 재구축

제목 요구

두 갈래 트리의 전차 역과 중차 역행 결과를 입력하고 두 갈래 트리를 재구성합니다. 전차와 중차 역행에 중복된 숫자가 포함되지 않는다고 가정합니다. 예를 들어 입력한 전차 역행 서열 {1,2,4,7,3,5,6,8}과 중차 역행 서열 {4,7,2,1,5,3,8,6}를 재구성합니다.

제목 해석

사고방식1:

분석

선서와 중서를 분석하고 선서: 1,2,4,7,3,5,6,8 중서: 4,7,2,1,5,3,8,6은 위의 선서 서열을 통해 루트 노드의 값이 1이라는 것을 확정할 수 있다. 중서 서열을 통해 우리는 4,7,2는 왼쪽 트리에 속하고 5, 3, 8, 6은 오른쪽 트리에 속하는 것과 같은 방법으로 우리는 좌우 트리를 하나의 전체로 삼아 점차적으로 구성할 수 있다.

코드 세그먼트

public static BinaryTreeNode constructCore(int[] preOrder , int[] inOrder) throws Exception {
        
        if(preOrder == null || inOrder == null) {
            return null ;
        }
        
        if(preOrder.length != inOrder.length) {
            throw new Exception("  ，  ") ;
        }
        
        BinaryTreeNode root = new BinaryTreeNode() ;
        
        for(int i = 0 ; i < preOrder.length ; i++) {
            
            if(inOrder[i] == preOrder[0]) {
                root.data = inOrder[i] ;
                
                System.out.println(root.getData());
                
                root.left = constructCore(Arrays.copyOfRange(preOrder, 1, 1+i) ,
                        Arrays.copyOfRange(inOrder, 0, i)) ;
                root.right = constructCore(Arrays.copyOfRange(preOrder, i+1, preOrder.length) ,
                        Arrays.copyOfRange(inOrder, i, inOrder.length)) ;
            }
            
        }
        
        return root ;
        
    }

테스트 코드

public static void main(String[] args) {
        
        int[] preOrder = {1,2,4,7,3,5,6,8} ;
        int[] inOrder = {4,7,2,1,5,3,8,6} ;
        
        try {
            BinaryTreeNode root = constructCore(preOrder, inOrder) ;
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

실행 결과

테스트 결과 없음

전체 소스 스탬프 소스 주소 보기