LeetCode 95. Unique Binary Search Trees II

For example, if the input is n, the title is to return all binary sorting trees consisting of 1, 2,... N. Each tree must contain the number of n.

This is the topic of permutation and combination of binary trees. Arrangements and combinations are often solved by DFS.

For example, input 3, that is to say, all trees with start = 1 and end = 3, abbreviated as t[1,3]. So consider these situations:

//t[a,b]={NULL} if a>b

root is 1, left is t[1, 0], right is t[2,3], left is {NULL}, right is two trees (see explanation below).

root is 2, left is t[1, 1], right is t[3,3]

root is 3, left is t[1, 2], right is t[4,3]

Similarly, for t[2,3], consider the following

root is 2, left is t[2, 1], right is t[3,3], you can see that there is only one.

root is 3, left is t[2, 2], right is t[4,3], and there is only one.

 

In addition, for DFS, map can be used to store calculated t[x,y] in order to prevent repeated computation. This is also a frequently used method.

 

class Solution {
public:
    vector<TreeNode*> generateTreesDFS(int start, int end, map<pair<int,int>, vector<TreeNode*>>& vecTreeMap) {
        vector<TreeNode*> subTree;
        if(vecTreeMap.find({start, end}) != vecTreeMap.end())
            return vecTreeMap[{start,end}];
        //a(start)
        //a(end)
        //ahd(subTree)
        if (start > end) subTree.push_back(NULL);
        else {
            for (int i = start; i <= end; ++i) {
                vector<TreeNode*> leftSubTree = generateTreesDFS(start, i - 1, vecTreeMap);
                vector<TreeNode*> rightSubTree = generateTreesDFS(i + 1, end, vecTreeMap);
                for (int j = 0; j < leftSubTree.size(); ++j) {
                    for (int k = 0; k < rightSubTree.size(); ++k) {
                        TreeNode *node = new TreeNode(i);
                        node->left = (leftSubTree)[j];
                        node->right = (rightSubTree)[k];
                        subTree.push_back(node);
                    }
                }
            }
            //dsp
        }
        vecTreeMap[{start, end}] = subTree;
        return subTree;
    }
    
    vector<TreeNode*> generateTrees(int n) {
        if(n==0) return {};
        map<pair<int,int>, vector<TreeNode*>> vecTreeMap;
        //amap(vecTreeMap, pair<int,int>, vector<TreeNode*>)
        return generateTreesDFS(1,n, vecTreeMap);
    }
};

Dynamic program running process: http://simpledsp.com/FS/Html/lc95.html

Tags: PHP Amap

Posted on Tue, 08 Oct 2019 22:20:32 -0700 by rocky