LeetCode95:Unique Binary Search Trees II

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.

confused what “{1,#,2,3}” means? > read more on how binary tree is serialized on OJ.<喎?/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPkhpZGUgVGFncyBUcmVlIER5bmFtaWMgUHJvZ3JhbW1pbmc8L3A+DQo8aHIgLz4NCjxwPtXitcDM4rK7ysfSu7XAtq/MrLnmu661xMzixL+jrLb4ysfSu7XAv8nS1Mq508O13bnpx/O94rXEzOLEv6GjPC9wPg0KPHA+1+6/qsq8v7S1vdXitcDM4s/rtb3Kx7fxv8nS1LC01dVVbmlxdWUgQmluYXJ5IFNlYXJjaCBUcmVlc9bQtcTLvMK3x/O94qOsvLS5zLao0ru49rj5vdq146Os09rKx7zZtqhuPTMsxMfDtMjnufvS1DHX986quPm92rXjo6zWu9Do0qrH83t91/fOqsv8tcTX89fTyvejrHsyLDN91/fOqsv8tcTT0tfTyvejrMi7uvPKudPDs8u3qNSt1PK+zb/J0tTH87P20tQxzqq4+b3ateO1xMv509DX08r3oaO1q8rHx/O94tfTyve1xM7KzOK6zdLUMc6quPm92rXjtcTL+dPQtv6y5svRy/fK97XEzsrM4rK7ysfNrNK7uPbOyszitvjT6zEmaGVsbGlwO27QzrPJtcTL+dPQtv6y5sr3ysfNrNK7uPbOyszioaM8YnIgLz4NCrj5vt3Jz8PmtcS31s7209rKx8/rtb3J6NLUaSZoZWxsaXA7Lmq1xNSqy9i5ubPJtcTL+dPQ19PK97XEuPm92rXjtcS8r7rPysdBW2ldW2pdo6zEx8O0v8nS1LHpwPppJmhlbGxpcDtq1tC1xMO/0ru49tSqy9hrLGkmbHQ7PWsmbHQ7PWqjrNSqy9hrtcTX89fTyvfKx2kuLmstMbm5s8m1xLb+subL0cv3yvfW0LXExLPSu8/uo6zUqsvYa7XE09LX08r3ysdrKzEmaGVsbGlwOy5qubmzybXEtv6y5svRy/fK99bQtcTEs9K7z+6jrM/W1NrV4rj219POyszivs26zdStyry1xM7KzOLKx82s0ru49s7KzOKjrL/J0tTKudPDtd256cfzveLBy6GjPGJyIC8+DQpydW50aW1lOjI0bXM8L3A+DQo8aHIgLz4NCjxwcmUgY2xhc3M9"brush:java;"> class Solution { public: vector generateTrees(int n) { vector result(1); if(n<=0) return result; return helper(1,n); } vector helper(int begin,int end) { vector result; if(begin==end) { result.push_back(new TreeNode(begin)); return result; } if(begin>end) return result; for(int i=begin;i<=end;i++) { vector leftRoot=helper(begin,i-1); vector rightRoot=helper(i+1,end); if(leftRoot.empty()) { for(int j=0;jleft=NULL; base->right=rightRoot[j]; result.push_back(base); } } else if(rightRoot.empty()) { for(int j=0;jleft=leftRoot[j]; base->right=NULL; result.push_back(base); } } else { for(int j=0;jleft=leftRoot[j]; base->right=rightRoot[k]; result.push_back(base); } } } } return result; } }

然後看到了可以避免進行左右子樹是否為空的判斷的一個優化。這個優化的主要技巧是使用含有一個NULL元素的vector，這樣就可以將左右子樹為是否為空統一起來了。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector generateTrees(int n) {
        return helper(1,n);
    }
    vector helper(int begin,int end)
    {
        vector result;
        if(begin==end)
        {
            result.push_back(new TreeNode(begin));
            return result;
        }
        if(begin>end)
        {
            result.push_back(NULL);
            return result;  
        }

        for(int i=begin;i<=end;i++)
        {
            vector leftRoot=helper(begin,i-1);
            vector rightRoot=helper(i+1,end);

            for(int j=0;jleft=leftRoot[j];
                        base->right=rightRoot[k];
                        result.push_back(base);
                 }
            }

        }

        return result;

    }

};