【Leetcode】每日一题2021/10/06

• 思路
  这个和昨天的中序和后序遍历很像，只是我们把后序改为了前序，前序的第一个点就是中序的分割点，分割以后，再除掉分割的那个元素，然后分割前序遍历。

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) {
            return null;
        }
        int val = preorder[0];
        int preLen = preorder.length, inLen = inorder.length;
        TreeNode node = new TreeNode(val);
        // 叶子节点
        if (preLen == 1) {
            return node;
        }
        // 找到分割点
        int index = 0;
        for (int i = 0; i < inLen; i++) {
            if (inorder[i] == val) {
                index = i;
                break;
            }
        }

        // 分割中序遍历
        int[] leftInorder = new int[index];
        int[] rightInorder = new int[inLen - index - 1];
        System.arraycopy(inorder, 0, leftInorder, 0, index);
        System.arraycopy(inorder, index + 1, rightInorder, 0, inLen - index - 1);

        // 分割前序遍历
        int[] leftPreorder = new int[index];
        int[] rightPreorder = new int[inLen - index - 1];   // 前序和中序子序列等长
        System.arraycopy(preorder, 1, leftPreorder, 0, index);
        System.arraycopy(preorder, index + 1, rightPreorder, 0, preLen - index - 1);

        // 进入下一层
        node.left = buildTree(leftPreorder, leftInorder);
        node.right = buildTree(rightPreorder, rightInorder);

        return node;
    }
}