1. 给表达式加括号

Leetcode-241. 为运算表达式设计优先级

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。

示例 1:

输入: "2-1-1"
输出: [0, 2]
解释: 
((2-1)-1) = 0 
(2-(1-1)) = 2

示例 2:

输入: "2*3-4*5"
输出: [-34, -14, -10, -10, 10]
解释: 
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10

解法：

• Java

使用递归，左右分别得到结果

class Solution {
   
    public List<Integer> diffWaysToCompute(String input) {
   
        List<Integer> res = new ArrayList<>();
        for (int i=0;i<input.length();i++) {
   
            char c = input.charAt(i);
            if (c=='+' || c=='-' || c=='*') {
   
                List<Integer> left = diffWaysToCompute(input.substring(0, i));
                List<Integer> right = diffWaysToCompute(input.substring(i+1));
                for (int a: left) {
   
                    for (int b: right) {
   
                        switch(c) {
   
                            case '+':
                                res.add(a+b);
                                break;
                            case '-':
                                res.add(a-b);
                                break;
                            case '*':
                                res.add(a*b);
                                break;
                        }
                    }
                }
            }
        }
        if (res.size() == 0) res.add(Integer.valueOf(input));
        return res;
    }
}

2. 不同的二叉搜索树

Leetcode-95. 不同的二叉搜索树 II

给定一个整数 n，生成所有由 1 … n 为节点所组成的二叉搜索树。

示例:

输入: 3
输出:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

解法：

• Java

class Solution {
   
    public List<TreeNode> generateTrees(int n) {
   
        if (n<1) return new ArrayList<>();
        return generateSubtrees(1, n);
    }
    private List<TreeNode> generateSubtrees(int s, int e) {
   
        List<TreeNode> res = new ArrayList<>();
        if (s>e) {
   
            res.add(null);
            return res;
        }
        // 选择一个根节点
        for (int i=s;i<=e;i++) {
   
            List<TreeNode> left = generateSubtrees(s, i-1);
            List<TreeNode> right = generateSubtrees(i+1, e);
            for (TreeNode l: left) {
   
                for (TreeNode r: right) {
   
                    TreeNode node = new TreeNode(i);
                    node.left = l;
                    node.right = r;
                    res.add(node);
                }
            }
        }
        return res;
    }
}