Wednesday, September 25, 2013

95. Unique Binary Search Trees II -----M

Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.

Example:

Input: 3
Output:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

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

 

Constraints:

  • 0 <= n <= 8

A:
难点就在于,左边和右边的子树是相乘关系,而非相加。
 所以,我们这里用了循环,每次create一个新的树(为节省空间,在两个for loop迭代的时候, 新树只有root才是新的,别的都是指向旧的指针)。
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if(n==0)
            return vector<TreeNode*>();
        return helper(1,n);
    }
private:
    vector<TreeNode*> helper(int a, int b){
        vector<TreeNode*> res;
        if(a>b){
            res.push_back(nullptr);
        }
        for(int i = a; i<=b;i++){
            auto vL = helper(a,i-1);
            auto vR = helper(i+1,b);
            for(auto ll : vL){
                for(auto rr : vR){
                    TreeNode * root = new TreeNode(i, ll, rr);
                    res.push_back(root);
                }
            }
        }
        return res;
    }
};

Mistakes:
1: 当左边或者右边的子树为空的时候,单纯利用两个for循环是不对的,因为这时候,可以把另一半直接加上就是了。
   这时候,要先判断 size() 是否为0    ----------- 代码见那几个for循环。

2: 当 input 为0,( 这个,就是题意没讲清楚了)。
Input: 0
Output: []
Expected: [{}]
 -----------当输入为0的时候,输出的结果格式不对,自己试着在all上加个null,也总是报错----
原因是--------- 前面有个return




Learned:

                    TreeNode * root = new TreeNode(i, ll, rr);
                    res.push_back(root);
这几句一开始是这样写的:
                                   TreeNode root(i, ll, rr);
                    res.push_back(&root);                可是这样不对, 不知道为什么

错误提示为:

ERROR: AddressSanitizer: stack-use-after-scope on address 0x7ffe12385e00 at pc 0x00000042003f bp 0x7ffe12384f80 sp 0x7ffe12384f78
READ of size 4 at 0x7ffe12385e00 thread T0
HINT: this may be a false positive if your program uses some custom stack unwind mechanism or swapcontext
(longjmp and C++ exceptions are supported)





1: 还是要动手写, 光自己在那里,玩儿着想,想不深。 也难以持续。
2: 因为自己本来的代码里面,存在大量的对象数据的拷贝。 其实,是可以仅仅用指针来解决的(虽然这道题目里面,也没有多用多少空间。但当对象大了之后, 还是很显著的)
所以,我原本的代码
for (int i = 0; i < alLeft.size(); i++) {
                    for (int j = 0; j < alRight.size(); j++) {
                        // create a new node, and copy left to right
                        TreeNode tmpTree = createNewTree(rootValue,
                                alLeft.get(i), alRight.get(j));
                        all.add(tmpTree);// add the values rooted at rootValue,
                                            // with one variation of left and
                                            // right child
                    } // end of loop for each of the right side subtree
                } // end of for loop for each of Left side subtree

远不如现在的代码;

No comments:

Post a Comment