검지offer프로그래밍 시험문제 자바 실현--4.두 갈래 나무를 재건하다

3306 단어 Java 기반
소경 오빠

4. 두 갈래 나무 재건


제목 설명: 두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하고 이 두 갈래 나무를 다시 만드십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.예를 들어 앞 순서 반복 시퀀스 {1,2,4,7,3,5,6,8}와 중간 순서 반복 시퀀스 {4,7,2,1,5,3,8,6}를 입력하면 두 갈래 트리를 재건하고 되돌려줍니다.

/**

* Definition for binary tree

* public class TreeNode {

*     int val;

*     TreeNode left;

*     TreeNode right;

*     TreeNode(int x) { val = x; }

* }

*/

public class Solution {

    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {

        TreeNode root = ConstructTree(pre, 0, pre.length - 1, in, 0, in.length - 1);

        return root;

    }

    public TreeNode ConstructTree(int[]pre, int start1,int end1, int[] in, int start2, int end2){

        if(start1 > end1 || start2 > end2)

            return null;

        int rootData = pre[start1];

        TreeNode head = new TreeNode(rootData);

        // 

        int rootIndex = findIndexInArray(in, rootData, start2, end2);

        int offSet = rootIndex - start2 - 1;

        // 

        TreeNode left = ConstructTree(pre, start1 + 1, start1 + 1 + offSet, in, start2, start2 + offSet);

        // 

        TreeNode right = ConstructTree(pre, start1 + offSet + 2, end1, in, rootIndex + 1, end2);

        head.left = left;

        head.right = right;

        return head;

    }

    public int findIndexInArray(int[]a, int x, int begin, int end) {

        for(int i = 0; i <= end; i++) {

            if(a[i] == x)

                return i;

        }

        return -1;

    }

}

좋은 웹페이지 즐겨찾기