小米笔试，二叉树，买东西，求思路

https://github.com/hhfgeg/myCodes/blob/master/codes/printMidTree.cpp 第二题

买东西：完全没背包，二叉树我是先递归构造二叉树 再中序输出

import java.util.Scanner; public class Package01_CostMBuyN {     public static void main(String[] args){         Scanner in = new Scanner(System.in);         int n = in.nextInt();         int[] ps = new int[n];         for(int i = 0; i < n; i++){             ps[i] = in.nextInt();         }         int m = in.nextInt();         int res = solution(ps, m ,n);         System.out.println(res);     }     public static int solution(int[] ps, int m, int n){         int res = -1;         int[][] dp = new int[n+1][m+1];         for(int j = 0; j < m+1; j ++){             dp[0][j] = -1;         }         for(int i = 0; i < n+1; i++){             dp[i][0] = 0;         }         for(int l = 1; l <= n; l++){             for(int r = 1; r <= m; r++){                 int min = Integer.MAX_VALUE;                 dp[l][r] = -1;                 for(int c = 0; c <= r ; c ++){                     int num = 0;                     if((r - c)%ps[l-1] != 0){                         continue;                     }                     int cur = (r - c)/ps[l-1];                     if(dp[l-1][c] == -1){                         continue;                     }else{                         num = dp[l - 1][c] + cur;                     }                     if(num < min ){                         min = num;                         dp[l][r] = min;                     }                 }             }         }         return dp[n][m];     } }

import java.util.*; public class Test{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.nextLine(); int index = 0, preIndex = 0; while(s.charAt(index) != '(')  //找到根节点 index++; TreeNode root = new TreeNode(null, null, null, s.substring(0,index)), tmp = root; index++; preIndex = index; char flag = '('; while(index < s.length()) { char c = s.charAt(index); if(c == '(' || c == ')' || c == ',') { if(flag == '(') { tmp.left = new TreeNode(null, null, null, s.substring(preIndex,index)); tmp.left.father = tmp; tmp = tmp.left; }else if(flag == ',') { tmp = tmp.father; tmp.right = new TreeNode(null, null, null, s.substring(preIndex,index)); tmp.right.father = tmp; tmp = tmp.right; }else if(flag == ')') { tmp = tmp.father; } preIndex = index+1; flag = c; } index++; } func(root); } private static void func(TreeNode root) { if(root.left != null)  func(root.left); System.out.print(root.val); if (root.right != null)  func(root.right); } } class TreeNode{ TreeNode left,right,father; String val; public TreeNode(TreeNode left, TreeNode right, TreeNode father, String val) { this.left = left; this.right = right; this.father = father; this.val = val; } }

第一题用栈蒙出来了 第二题dp🤣