1. Different Ways to Add Parentheses (Medium)

Leetcode / 力扣

  1. Input: "2-1-1".
  3. ((2-1)-1) = 0
  4. (2-(1-1)) = 2
  6. Output : [0, 2]
  1. public List<Integer> diffWaysToCompute(String input) {
  2.     List<Integer> ways = new ArrayList<>();
  3.     for (int i = 0; i < input.length(); i++) {
  4.         char c = input.charAt(i);
  5.         if (c == '+' || c == '-' || c == '*') {
  6.             List<Integer> left = diffWaysToCompute(input.substring(0, i));
  7.             List<Integer> right = diffWaysToCompute(input.substring(i + 1));
  8.             for (int l : left) {
  9.                 for (int r : right) {
  10.                     switch (c) {
  11.                         case '+':
  12.                             ways.add(l + r);
  13.                             break;
  14.                         case '-':
  15.                             ways.add(l - r);
  16.                             break;
  17.                         case '*':
  18.                             ways.add(l * r);
  19.                             break;
  20.                     }
  21.                 }
  22.             }
  23.         }
  24.     }
  25.     if (ways.size() == 0) {
  26.         ways.add(Integer.valueOf(input));
  27.     }
  28.     return ways;
  29. }

2. 不同的二叉搜索树

  1. Unique Binary Search Trees II (Medium)

Leetcode / 力扣

给定一个数字 n，要求生成所有值为 1…n 的二叉搜索树。

  1. Input: 3
  2. Output:
  3. [
  4.   [1,null,3,2],
  5.   [3,2,null,1],
  6.   [3,1,null,null,2],
  7.   [2,1,3],
  8.   [1,null,2,null,3]
  9. ]
  10. Explanation:
  11. The above output corresponds to the 5 unique BST's shown below:
  13.    1         3     3      2      1
  14.     \       /     /      / \      \
  15.      3     2     1      1   3      2
  16.     /     /       \                 \
  17.    2     1         2                 3
  1. public List<TreeNode> generateTrees(int n) {
  2.     if (n < 1) {
  3.         return new LinkedList<TreeNode>();
  4.     }
  5.     return generateSubtrees(1, n);
  6. }
  8. private List<TreeNode> generateSubtrees(int s, int e) {
  9.     List<TreeNode> res = new LinkedList<TreeNode>();
  10.     if (s > e) {
  11.         res.add(null);
  12.         return res;
  13.     }
  14.     for (int i = s; i <= e; ++i) {
  15.         List<TreeNode> leftSubtrees = generateSubtrees(s, i - 1);
  16.         List<TreeNode> rightSubtrees = generateSubtrees(i + 1, e);
  17.         for (TreeNode left : leftSubtrees) {
  18.             for (TreeNode right : rightSubtrees) {
  19.                 TreeNode root = new TreeNode(i);
  20.                 root.left = left;
  21.                 root.right = right;
  22.                 res.add(root);
  23.             }
  24.         }
  25.     }
  26.     return res;
  27. }

Leetcode 题解 - 分治 - 图1