public class T3 {
    List<Long> list = new ArrayList<>();
    public long[] buildPostOrder (long[] preorderData, long[] inorderData) {
        // write code here
        TreeNode root = rebuildTree(preorderData, inorderData);
        dfs(root);
        long[] res = new long[list.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    private void dfs(TreeNode root) {
        if (root == null){
            return;
        }

        dfs(root.left);
        dfs(root.right);
        list.add(root.value);
    }

    private TreeNode rebuildTree(long[] preorderData, long[] inorderData) {
        int len = preorderData.length - 1;
        return rebuildTreeSolution(preorderData, 0, len, inorderData, 0, len + 1);
    }

    private TreeNode rebuildTreeSolution(long[] preorderData, int preStart, int preEnd,
                                         long[] inorderData, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) return null;
        // 重建根节点
        TreeNode root = new TreeNode(preorderData[preStart]);

        // 找到根节点在中序中的位置，作为左右子树划分的依据
        int index = 0;
        long tmp = preorderData[preStart];
        for (int i = inStart; i < inorderData.length; i++) {
            if (inorderData[i] == tmp) {
                break;
            }
            index++;
        }
        // 递归重建左节点右节点
        root.left = rebuildTreeSolution(preorderData, preStart + 1, preStart + index + 1,
                inorderData, inStart, inStart + index - 1);
        root.right = rebuildTreeSolution(preorderData, preStart + index + 1, preEnd,
                inorderData, inStart + index + 1, inEnd);
        return root;
    }
}



public class T2 {
    List<List<Integer>> set = new ArrayList<>();
    public String largestMultipleOfThree (ArrayList<Integer> digits) {
        List<Integer> res = null;
        getSubSet(digits, 0, new ArrayList<>());
        set.sort((l1, l2)->l2.size() - l1.size());
        System.out.println(set);
        for (List<Integer> list :
                set) {
            int sum = list.stream().mapToInt(integer -> integer).sum();
            if (sum % 3 == 0){
                res = list;
                break;
            }
        }

        if (res == null){
            return "";
        }else {
            res.sort((n1,n2)->n2-n1);
            if (res.get(0) == 0) return "0";
            StringBuilder sb = new StringBuilder();
            for (int i :
                    res) {
                sb.append(i);
            }
            return sb.toString();
        }
    }

    private void getSubSet(ArrayList<Integer> digits, int pos, ArrayList<Integer> tmp) {
        if (tmp.size() > 0){
            set.add(new ArrayList<>(tmp));
        }

        for (int i = pos; i < digits.size(); i++) {
            tmp.add(digits.get(i));
            getSubSet(digits, i + 1, tmp);
            tmp.remove(tmp.size() - 1);
        }
    }
}