이미 알고 있는 두 갈래 나무의 앞 순서와 중간 순서, 두 갈래 나무 재건_메모

제목은 다음과 같습니다.
두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하십시오. 이 두 갈래 나무를 다시 만드십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.예를 들어 앞 순서 반복 시퀀스 {1,2,4,7,3,5,6,8}와 중간 순서 반복 시퀀스 {4,7,2,1,5,3,8,6}를 입력하면 두 갈래 트리를 재건하고 되돌려줍니다.
분석:
두 갈래 나무의 앞 순서는 뿌리 노드에 접근한 다음에 왼쪽 트리를 앞순서로 훑어보고 오른쪽 트리를 앞순서로 훑어보는 것이다.
중차원 역행 순서는 중차원 역행 루트 노드의 왼쪽 트리, 그리고 루트 노드에 접근하여 마지막 중차원 역행 오른쪽 트리입니다.
1. 두 갈래 나무의 앞차례 역행 서열은 반드시 이 나무의 뿌리 노드이다
2. 중서열 반복 시퀀스 중 뿌리 노드 앞에는 반드시 이 나무의 왼쪽 나무가 있고 뒤에는 이 나무의 오른쪽 나무가 있다
위에서 알 수 있듯이 제목에서 앞뒤로 흐르는 첫 번째 노드 {1}은 반드시 이 두 갈래 나무의 뿌리 노드이다. 중간 순서대로 흐르는 시퀀스에 따라 중간 순서대로 흐르는 시퀀스 중 노드 {1} 이전의 {4,7,2}는 이 두 갈래 나무의 왼쪽 자목이고 {5,3,8,6}는 이 두 갈래 나무의 오른쪽 자목이다.그리고 왼쪽 트리에 대해 순서 하위 서열 {2,4,7}과 중간 서열 하위 서열 {4,7,2}를 새로운 순서 하위 서열과 중간 서열 하위 서열로 보십시오.이때 이 두 서열에 대해 이 자수의 뿌리 노드는 {2}이고 이 자수의 왼쪽 자수는 {4,7}이며 오른쪽 자수는 비어 있다. 이렇게 귀속한다(현재 자수를 나무로 하고 상기 절차에 따라 분석한다).{5,3,8,6} 이 우자나무의 분석도 이렇다.
코드는 다음과 같습니다.

class TreeNode {
	     int val;
	      TreeNode left;
	      TreeNode right;
	      TreeNode(int x) { val = x; }
	  }
public class TestRecoverBinaryTree {
	public TreeNode reConstructBinaryTree(int [] preOrder,int [] inOrder) 
	{
		int pLen = preOrder.length;
		int iLen = inOrder.length;
		if(pLen==0 && iLen==0)
        {
            return null;
        }
        return  btConstruct( preOrder, inOrder, 0, pLen-1,0, iLen-1);
    }
	// ，pStart pEnd ；
	//iStart iEnd 。
	public TreeNode btConstruct(int[] preOrder, int[] inOrder, int pStart, int pEnd,int iStart,int iEnd)
	{
		// 
		TreeNode tree = new TreeNode(preOrder[pStart]);
		tree.left = null;
		tree.right = null;
		if(pStart == pEnd && iStart == iEnd)
		{
			return tree;
		}
		int root = 0;
		// 
		for(root=iStart; root0)
		{
			tree.left = btConstruct(preOrder, inOrder,  pStart+1,  pStart+leftLength, iStart, root-1);
		}
		// 
		if(rightLength>0)
		{
			tree.right = btConstruct(preOrder, inOrder,  pStart+leftLength+1,  pEnd, root+1, iEnd);
		}
		return tree;
	}
}

참고:
이미 알고 있는 전차와 중차가 두루 돌아다니면 두 갈래 나무 한 그루를 확정할 수 있다.이미 알고 있는 중서와 후서가 두루 돌아다니면 두 갈래 나무 한 그루를 확정할 수 있다.그러나 전차와 후차가 두루 다니는 것으로 알려져 두 갈래 나무 한 그루를 확정할 수 없다.