면접문제 (7) 두 갈래 나무 재건

제목: 두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하십시오. 이 두 갈래 나무를 다시 만드십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.트리 노드의 정의는 다음과 같습니다.

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
 }

사고방식: 앞의 순서대로 결과를 훑어보는 첫 번째 숫자는 두 갈래 나무 뿌리 노드의 값입니다. 중간의 순서대로 훑어보는 결과에서 이 값을 찾았습니다. 왼쪽의 숫자는 뿌리 노드 왼쪽의 트리 노드의 값이고 오른쪽의 숫자는 뿌리 노드 오른쪽의 트리 노드의 값입니다.따라서 앞의 반복 결과에서 왼쪽 트리와 오른쪽 트리의 노드에 대응하는 반복 결과의 하위 서열을 확정할 수 있다.다시 전차 역행 결과와 중차 역행 결과의 하위 서열에 대해 같은 알고리즘을 사용하면 두 갈래 트리를 재구성할 수 있다.
코드(우객망 AC에서):

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

        // 
        if(pre == null || in == null || pre.length != in.length)
            return null;

        return reConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
    }

    private TreeNode reConstructBinaryTree(int[] pre, int preBegin, int preEnd, int[] in, int inBegin, int inEnd){
        TreeNode root = new TreeNode(pre[preBegin]);

        //  
        if(preBegin == preEnd){
            if(inBegin == inEnd && pre[preBegin] == in[inBegin])
                return root;
            else
            return null;
        }

        //  
        int rootPos = inBegin;
        for(int i = inBegin; i <= inEnd; i++){
            if(in[i] == pre[preBegin])
            {
                rootPos = i;
                break;
            }
        }

        //  
        if(rootPos == inEnd && in[rootPos] != pre[preBegin])
            return null;

        if(rootPos > inBegin){
            root.left = reConstructBinaryTree(pre, preBegin + 1, preBegin + rootPos - inBegin, in, inBegin, rootPos - 1);
        }

        if(rootPos < inEnd){
            root.right = reConstructBinaryTree(pre, preBegin + rootPos - inBegin + 1, preEnd, in, rootPos + 1, inEnd);
        }

        return root;
    }
}