分治与递归

在刷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 *.

Paste_Image.png

在思考这道题的过程中，我一直没有考虑到使用分治和递归思想的，总是想着统计也就是遍历的方法来解决这个问题，但是这样的话，要考虑的情况太多了，而且也不好验证自己是不是考虑到了所有的情况，参考了别人的思路，感觉这个思路可以解决类似的很多 问题，这里挑出两道，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.

Paste_Image.png

解题思路：<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;
    }
};