树的中序遍历+递归

中缀表达式可以转化成一个树，叶节点放数字，非叶节点放运算符。

将整个表达式看成是不同树的中序遍历的结果。加括号只不过是改变树的形态，不影响中序遍历的结果，这样我们就可以任意的枚举每个运算符作为树的根节点。类似lc95题

1. 枚举表达式。
2. 如果遇到运算符，就可以将该运算符看成树的根节点，先处理左右两边能得到的所有结果，然后进行乘法原理进行组合结果。
3. 最终若答案数组为0，则说明表达式只有一个数字，无运算符。

时间复杂度$O(C_N)$

AC代码

class Solution {
public:
    vector<int> diffWaysToCompute(string exp) {
        int n = exp.size();
        vector<int> res;
        for (int i = 0 ; i < n ; i ++) {
            char c = exp[i];
            if (c == '+' || c == '-' || c == '*') {
                auto left = diffWaysToCompute(exp.substr(0, i));
                auto right = diffWaysToCompute(exp.substr(i + 1, n - i - 1));
                for (auto a : left) 
                    for (auto b : right) {
                        if (c == '+') res.push_back(a + b);
                        else if (c == '-') res.push_back(a - b);
                        else res.push_back(a * b);
                    }
            }
        }
        //特判表达式只有数字
        if (res.size() == 0) res.push_back(stoi(exp.substr(0)));
        return res;
    }
};