腾讯音乐 含有重复元素的前序和中序的二叉树构造

    public ArrayList<TreeNode> getBinaryTrees(ArrayList<Integer> preOrder, ArrayList<Integer> inOrder) {
        int n = preOrder.size();
        return createTree(preOrder, inOrder, 0, n - 1, 0, n - 1);
    }

    private ArrayList<TreeNode> createTree(ArrayList<Integer> preOrder, ArrayList<Integer> inOrder, int pl, int ph, int il, int ih) {
        if (pl > ph) {
            return new ArrayList<>();
        }
        ArrayList<TreeNode> res = new ArrayList<>();
        for (int i = il; i <= ih; i++) {
            if (preOrder.get(pl).equals(inOrder.get(i))) {
                int leftNum = i - il;
                ArrayList<TreeNode> leftChildes = createTree(preOrder, inOrder, pl + 1, pl + leftNum, il, i- 1);
                ArrayList<TreeNode> rightChildes = createTree(preOrder, inOrder, pl + leftNum + 1, ph, i + 1, ih);
                for (TreeNode leftChild : leftChildes) {
                    for (TreeNode rightChild : rightChildes) {
                        TreeNode p = new TreeNode(preOrder.get(pl));
                        p.left = leftChild;
                        p.right = rightChild;
                        res.add(p);
                    }
                }
            }
        }
        return res;
    }