검지 Offer - 두 갈래 나무 재건

제목 설명

두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하십시오. 이 두 갈래 나무를 다시 만드십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.예를 들어 앞 순서 반복 시퀀스 {1,2,4,7,3,5,6,8}와 중간 순서 반복 시퀀스 {4,7,2,1,5,3,8,6}를 입력하면 두 갈래 트리를 재건하고 되돌려줍니다.
문제 풀이 사상: 귀속 사상!앞 순서와 중간 순서를 사용하면 유일한 두 갈래 나무를 확인할 수 있습니다. 앞 순서를 통해 뿌리 노드가 1인 것을 알 수 있습니다. 그리고 중간 순서를 통해 왼쪽 나무가 {4, 7, 2}이고 오른쪽 나무가 {5, 3, 8, 6}라는 것을 알 수 있습니다.이어서 귀속사상을 통해 {4, 7, 2} 중 4를 뿌리 노드로 하고 좌우 나무를 계속 나누어 {5, 3, 8, 6}에 대해서도 똑같이 조작하여 반복이 끝날 때까지 한다.
귀속구해를 생각하기 쉽지만 코드를 쓰기 시작할 때 렉이 걸릴 수 있습니다. 어디서부터 손을 대야 하는지, 얼마나 많은 파라미터를 전달해야 하는지 모르겠습니다. 본제의 가장 중요한 것은 왼쪽 나무와 오른쪽 나무가 수조 간의 범위를 확정하고 다음 단계에 누가 뿌리이고 누가 왼쪽이고 오른쪽인지 판단하는 것입니다.아니면 Arrays를 사용할 수 있습니다.copy OfRange 복제 수조로 왼쪽 트리와 오른쪽 트리를 단독으로 복사하여 귀속합니다.

Java 최적

	public class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode(int x) { val = x; }
     }
    public TreeNode findBinaryTree(int[] pre, int preStart, int preEnd, int[] in ,int inStart, int inEnd){
        //  
        if(preStart>preEnd || inStart>inEnd)
            return null;

        //  
        TreeNode root = new TreeNode(pre[preStart]);

        for(int i=inStart;i<=inEnd;i++){
            if(in[i]==pre[preStart]){
                // i-startIn  
                root.left = findBinaryTree(pre, preStart+1, i-inStart+preStart, in, inStart, i-1);
                // (i-startIn+startPre)+1： 
                root.right = findBinaryTree(pre, i-inStart+preStart+1, preEnd, in, i+1, inEnd);
            }
        }
        return root;
    }
	//  
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        TreeNode root = findBinaryTree(pre, 0, pre.length-1, in, 0, in.length-1);
        return root;
    }

Arrays를 사용합니다.copyOfRange

import java.util.*;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
           if(pre.length == 0|| pre.length!=in.length){
                return null;
            }
            TreeNode node = new TreeNode(pre[0]);
            for(int i = 0; i < in.length; i++){
                if(pre[0] == in[i]){
                    node.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i));
                    node.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1,in.length));
                }
            }
            return node;
        }
}