제목 출처:https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
문제 설명

105. Construct Binary Tree from Preorder and Inorder Traversal

Medium
155841FavoriteShare
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:You may assume that duplicates do not exist in the tree.
For example, given
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:
    3
  /\
  9  20
   / \
   15   7
------------------------------------------------------------
제목
두 갈래 나무의 선차적 범람과 중차적 범람을 정하여 이 두 갈래 나무를 구성한다.(알려진 두 갈래 나무의 노드마다 값이 다르다)
------------------------------------------------------------
생각
차례로 실현되다.역귀 함수는 하위 트리의 선순 역행과 중순 역행을 통해 하위 트리를 구성하고 하위 트리의 루트 노드를 되돌려줍니다.구체적으로 말하면 귀속 함수의 입력은 선차적 역류수조, 중차적 역류수조, 서브트리가 선차적 역류수조의 시작주소, 서브트리가 중차적 역류수조의 시작주소, 서브트리가 선차적/중차적 역류수조의 길이이며, 반환값은 서브트리의 루트 노드이다.역귀 함수 안에서 먼저 선차적 역류수조와 서브트리가 선차적 역류수조의 시작 주소를 통해 서브트리의 루트 노드를 구성한 다음에 중차적 역류수조에서 서브트리 루트 노드의 값을 찾아낸다. 서브트리 루트 노드가 중차적 역류수조의 주소와 중차적 역류수조의 시작 주소로 왼쪽 서브트리의 길이를 계산한 다음에 서브트리가 선차/중차적 역류수조의 길이에 따라 오른쪽 서브트리의 길이를 계산할 수 있다.이로써 좌자수와 우자수를 구성하여 좌자수의 뿌리 노드를 현재 자수 뿌리 노드의 왼쪽 자녀로, 우자수의 뿌리 노드를 현재 자수 뿌리 노드의 오른쪽 자녀로 분류할 수 있다.마지막으로 현재 하위 트리의 루트 노드를 되돌려줍니다.
[일거수일투족]
이미 알고 있는 중서적 반복과 후서적 반복도 두 갈래 나무를 재건할 수 있다.
그러나 선차역과 후차역은 유일한 두 갈래 나무를 만들 수 없는 것으로 알려져 여러 가지 상황이 있을 수 있다.다음은 다음과 같은 예입니다.
   1                    1
/                       \
2                         2
두 나무의 선차적 역력은 모두[1,2]이고 후차적 역력은 모두[2,1]이다.이를 통해 알 수 있듯이 선차적 역류와 후차적 역류가 함께 놓여 두 갈래 나무를 만들 수 없는 이유는 왼쪽 나무나 오른쪽 나무가 비어 있는 상황이 존재할 때 뿌리 노드를 제외한 부분이 왼쪽 나무에 속하는지 오른쪽 나무에 속하는지 확인할 수 없다.
------------------------------------------------------------
코드

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    /**
    find index of {@code value} in array {@code arr} beginning at {@code begin} with valid length {@code len}
    */
    private int findVal(int[] arr, int begin, int len, int value)
    {
        for (int i = begin; i < begin + len; i++)
        {
            if (arr[i] == value)
            {
                return i;
            }
        }
        return -1;
    }
    
    /**
    construct a subtree defined by preorder[prehead:prehead+sublen] & inorder[inhead:inhead+sublen]
    {@code preorder}: preorder array
    {@code inorder}: inorder array
    {@code prehead}: begin of subtree in {@code preorder}
    {@code inhead}: begin of subtree in {@code inorder}
    {@code sublen}: length of subtree
    return: root node of subtree
    */
    private TreeNode subTree(int[] preorder, int[] inorder, int prehead, int inhead, int sublen)
    {
        if (sublen == 0)
        {
            return null;
        }
        TreeNode root = new TreeNode(preorder[prehead]);
        int in_root = findVal(inorder, inhead, sublen, preorder[prehead]);
        root.left = subTree(preorder, inorder, prehead+1, inhead, in_root - inhead);
        root.right = subTree(preorder, inorder, prehead+1+in_root-inhead, in_root+1, sublen-in_root+inhead-1);
        return root;
    }
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return subTree(preorder, inorder, 0, 0, preorder.length);
    }
}