두 갈래 나무를 재건하는 사고방식으로 돌아가다

(1) 앞 순서 목록(루트 좌우)과 중간 순서 목록(왼쪽과 오른쪽)을 통해 두 갈래 트리 사고방식의 앞 순서를 반복합니다. 첫 번째 숫자는 두 갈래 트리의 루트 노드입니다.중차 역행 시퀀스에서 루트 노드의 값은 시퀀스 중간에 있고 왼쪽 트리의 노드의 값은 루트 노드의 값 왼쪽에 있고 오른쪽 트리의 노드의 값은 루트 노드의 값 오른쪽에 있습니다.두 갈래 나무의 이 성질에 따라 귀속 방법을 채택하면 두 갈래 나무를 재건할 수 있다.

/**
 * 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 node=reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
        return node;
    }
    public TreeNode reConstructBinaryTree(int [] pre,int ps,int pe,int [] in,int is,int ie) {
        if(ps>pe)// 
            return null;
        int value=pre[ps];
        int index=is;
        while(index<=ie&&in[index]!=value)// index 
            index++;
        TreeNode node=new TreeNode(pre[startPre]);
        node.left=reConstructBinaryTree(pre,ps+1,ps+index-is,in,is,index-1);
        node.right=reConstructBinaryTree(pre,ps+index-is+1,pe,in,index+1,ie);
        return node;
    }
}

(2) Java의 Arrays를 사용합니다.copyOfRange 두 갈래 나무 재건 작업 완료
Arrays.copy OfRange(T[]original, int from, int to)는 원시적인 그룹 original을 작은 그룹 from부터 복사하여 작은 그룹 to로 복사하여 새로운 그룹을 생성합니다.여기에는 아래표from가 포함되어 있으며, 아래표to는 포함되지 않습니다.

 public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length == 0 || in.length == 0){
            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;

    }

다음으로 전송:https://www.cnblogs.com/tongxupeng/p/10259557.html