在刷leetcode的过程中，感觉总结方法是很重要的，因为很多类型一样的题目，采用的完全是同样的算法，今天要说的这两道都是采用分治和递归的思想来解决问题的。看看这种方法能不能代入到其他解题中。
题目一：
Different Ways to Add Parentheses
Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.
在思考这道题的过程中，我一直没有考虑到使用分治和递归思想的，总是想着统计也就是遍历的方法来解决这个问题，但是这样的话，要考虑的情况太多了，而且也不好验证自己是不是考虑到了所有的情况，参考了别人的思路，感觉这个思路可以解决类似的很多 问题，这里挑出两道，mark一下。
针对题目一，其是分别将每一个运算符的左右各作为一个整体，然后在通过该运算符得到结果，及：<b>左右子串分别计算所有可能，然后全排列。</b>
代码：
class Solution {
public:
vector<int> diffWaysToCompute(string input) {//统计所有运算符前后计算的所有可能，然后全排列
vector<int> ret;
for(int i = 0; i < input.size(); i ++){
if(input[i] == '+' || input[i] == '-' || input[i] == '*'){
vector<int> left = diffWaysToCompute(input.substr(0, i));
vector<int> right = diffWaysToCompute(input.substr(i + 1));
for(int j = 0; j < left.size(); j ++){
for(int k = 0; k < right.size(); k ++){
if(input[i] == '+')
ret.push_back(left[j] + right[k]);
if(input[i] == '-')
ret.push_back(left[j] - right[k]);
if(input[i] == '*')
ret.push_back(left[j] * right[k]);
}
}
}
}
if(ret.empty())
ret.push_back(atoi(input.c_str()));
return ret;
}
};
与该题解题思路异曲同工的是题目<b>Unique Binary Search Trees II</b>
Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.
For example,Given n = 3, your program should return all 5 unique BST's shown below.
解题思路：<b>递归思想，依次选择根节点，对左右子序列再分别建树。
由于左右子序列建树的结果也可能不止一种，需要考虑所有搭配情况。</b>
与上一题的<b>先计算左右子树的所有可能，然后全排列</b>思路相同
代码：
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<TreeNode *> generateTrees(int n) {
return Helper(1, n);
}
vector<TreeNode *> Helper(int begin, int end)
{
vector<TreeNode *> ret;
if(begin > end)
ret.push_back(NULL);
else if(begin == end)
{
TreeNode* node = new TreeNode(begin);
ret.push_back(node);
}
else
{
for(int i = begin; i <= end; i ++)
{//root
vector<TreeNode *> left = Helper(begin, i-1);
vector<TreeNode *> right = Helper(i+1, end);
for(int l = 0; l < left.size(); l ++)
{
for(int r = 0; r < right.size(); r ++)
{
//new tree
TreeNode* root = new TreeNode(i);
root->left = left[l];
root->right = right[r];
ret.push_back(root);
}
}
}
}
return ret;
}
};
