95. Unique Binary Search Trees II

Given an integer 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.

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

解法類似 241題:http://www.reibang.com/p/91b3c4352b43

Solution1:Divide and Conquer

以每個(gè)num=0...n都嘗試作為起點(diǎn)敢会,以num分成左右兩部分part1 for [0..num - 1], part2 for [num + 1, n] (Divide)阱冶,recursiely計(jì)算part1和part2的建樹結(jié)果茎用,再將這兩個(gè)組合結(jié)果Conquer構(gòu)成從當(dāng)前num分的結(jié)果描验。
Time Complexity: 框沟? Space Complexity: 梁呈?

Solution2:Divide and Conquer + Hashmap

Solution1中含有重復(fù)計(jì)算嘁锯,2在Solution1的基礎(chǔ)上 將已求過的[start, end]的結(jié)果 Map<String, List<TreeNode>> cached_tree保存下來掂林,緩存避免重復(fù)計(jì)算粘我。
Time Complexity: 鼓蜒? Space Complexity: 痹换?

Solution3:DP寫法

ret[n] 保存到n的結(jié)果(所有的unique BST)
根據(jù)96. Unique Binary Search Trees: http://www.reibang.com/p/a49119ef97c3
的DP遞推表達(dá)式

G(n): the number of unique BST for a sequence of length n.
F(i, n), 1 <= i <= n: the number of unique BST, where the number i is the root of BST, and the sequence ranges from 1 to n.

G(0)=1, G(1)=1. 
G(n) = F(1, n) + F(2, n) + ... + F(n, n). 
F(i, n) = G(i-1) * G(n-i)   1 <= i <= n 
So, 
=>    G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0) 

思路相同,這不過這里是把G當(dāng)作實(shí)際的BSTs都弹,G(0) 和 G(n-1) 做組合娇豫,G(1) * G(n-2)做組合,...都加到結(jié)果中畅厢。做組合時(shí)樹:node.value = j, 左側(cè)的是left children冯痢,右側(cè)的是right children(需shift),
Example G(4) 如下圖所示:

屏幕快照 2017-09-04 下午11.43.50.png

n = sum of the total number of unique binary trees
Time Complexity: n框杜? Space Complexity: n浦楣?

Solution1 Code:

class Solution1 {
    public List<TreeNode> generateTrees(int n) {
        if(n == 0) return new ArrayList<TreeNode>();
        return genTrees(1,n);
    }
        
    public List<TreeNode> genTrees (int start, int end) {
        List<TreeNode> list = new ArrayList<TreeNode>();
        if(start > end) list.add(null);
        else if(start == end) list.add(new TreeNode(start));
        else {
            // start < end
            List<TreeNode> left,right;
            for(int i = start; i <= end; i++) {
                // Divide
                left = genTrees(start, i - 1);
                right = genTrees(i + 1, end);

                // Conquer
                for(TreeNode lnode: left) {
                    for(TreeNode rnode: right) {
                        TreeNode root = new TreeNode(i);
                        root.left = lnode;
                        root.right = rnode;
                        list.add(root);
                    }
                }
            }
        }
        return list;
    }
}

Solution2 Code:

class Solution2 {
    public List<TreeNode> generateTrees(int n) {
        if(n == 0) return new ArrayList<TreeNode>();
        return genTrees(1,n);
    }
    
    private Map<String, List<TreeNode>> cached_tree = new HashMap<>();
        
    public List<TreeNode> genTrees (int start, int end) {
        // find if there has been cached already
        String key = "" + start + "." + end;
        if(cached_tree.containsKey(key)) return cached_tree.get(key);
        
        List<TreeNode> list = new ArrayList<TreeNode>();
        if(start > end) list.add(null);
        else if(start == end) list.add(new TreeNode(start));
        else {
            // start < end
            List<TreeNode> left,right;
            for(int i = start; i <= end; i++) {
                // Divide
                left = genTrees(start, i - 1);
                right = genTrees(i + 1, end);

                // Conquer
                for(TreeNode lnode: left) {
                    for(TreeNode rnode: right) {
                        TreeNode root = new TreeNode(i);
                        root.left = lnode;
                        root.right = rnode;
                        list.add(root);
                    }
                }
            }
        }
        cached_tree.put(key, list);
        return list;
    }
}

Solution3 Code:

class Solution3 {
    // G(0)=1, G(1)=1. 
    // G(n) = F(1, n) + F(2, n) + ... + F(n, n). 
    // F(i, n) = G(i-1) * G(n-i)   1 <= i <= n 
    // =>
    // G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0) 
    
    public List<TreeNode> generateTrees(int n) {
        if(n == 0) return new ArrayList<TreeNode>();
        
        // dp init
        List<TreeNode>[] res = new List[n+1];
        res[0] = new ArrayList();
        res[0].add(null);
        res[1] = new ArrayList();
        res[1].add(new TreeNode(1));
        
        // dp
        for(int i = 2; i <= n; i++){
            res[i] = new ArrayList();
            for(int j = 1; j <= i; j++){
                for(TreeNode nodeL: res[j - 1]){
                    for(TreeNode nodeR: res[i - j]){
                        TreeNode node = new TreeNode(j);
                        node.left = nodeL;
                        node.right = clone(nodeR, j);
                        res[i].add(node);
                    }
                }
            }
        }
        return res[n];
    }
    
    private TreeNode clone(TreeNode n, int offset) {
        if (n == null) {
            return null;
        }
        TreeNode node = new TreeNode(n.val + offset);
        node.left = clone(n.left, offset);
        node.right = clone(n.right, offset);
        return node;
    }
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市霸琴,隨后出現(xiàn)的幾起案子椒振,更是在濱河造成了極大的恐慌,老刑警劉巖梧乘,帶你破解...
    沈念sama閱讀 218,607評(píng)論 6 507
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件澎迎,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡选调,警方通過查閱死者的電腦和手機(jī)夹供,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,239評(píng)論 3 395
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來仁堪,“玉大人哮洽,你說我怎么就攤上這事∠夷簦” “怎么了鸟辅?”我有些...
    開封第一講書人閱讀 164,960評(píng)論 0 355
  • 文/不壞的土叔 我叫張陵,是天一觀的道長莺葫。 經(jīng)常有香客問我匪凉,道長,這世上最難降的妖魔是什么捺檬? 我笑而不...
    開封第一講書人閱讀 58,750評(píng)論 1 294
  • 正文 為了忘掉前任再层,我火速辦了婚禮,結(jié)果婚禮上堡纬,老公的妹妹穿的比我還像新娘聂受。我一直安慰自己,他們只是感情好烤镐,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,764評(píng)論 6 392
  • 文/花漫 我一把揭開白布蛋济。 她就那樣靜靜地躺著,像睡著了一般炮叶。 火紅的嫁衣襯著肌膚如雪碗旅。 梳的紋絲不亂的頭發(fā)上鹊杖,一...
    開封第一講書人閱讀 51,604評(píng)論 1 305
  • 那天,我揣著相機(jī)與錄音扛芽,去河邊找鬼。 笑死积瞒,一個(gè)胖子當(dāng)著我的面吹牛川尖,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播茫孔,決...
    沈念sama閱讀 40,347評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼叮喳,長吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來了缰贝?” 一聲冷哼從身側(cè)響起馍悟,我...
    開封第一講書人閱讀 39,253評(píng)論 0 276
  • 序言:老撾萬榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎剩晴,沒想到半個(gè)月后锣咒,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,702評(píng)論 1 315
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡赞弥,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,893評(píng)論 3 336
  • 正文 我和宋清朗相戀三年毅整,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片绽左。...
    茶點(diǎn)故事閱讀 40,015評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡悼嫉,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出拼窥,到底是詐尸還是另有隱情戏蔑,我是刑警寧澤,帶...
    沈念sama閱讀 35,734評(píng)論 5 346
  • 正文 年R本政府宣布鲁纠,位于F島的核電站总棵,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏房交。R本人自食惡果不足惜彻舰,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,352評(píng)論 3 330
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望候味。 院中可真熱鬧刃唤,春花似錦、人聲如沸白群。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,934評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽帜慢。三九已至笼裳,卻和暖如春唯卖,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背躬柬。 一陣腳步聲響...
    開封第一講書人閱讀 33,052評(píng)論 1 270
  • 我被黑心中介騙來泰國打工拜轨, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人允青。 一個(gè)月前我還...
    沈念sama閱讀 48,216評(píng)論 3 371
  • 正文 我出身青樓橄碾,卻偏偏與公主長得像,于是被迫代替她去往敵國和親颠锉。 傳聞我的和親對(duì)象是個(gè)殘疾皇子法牲,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,969評(píng)論 2 355

推薦閱讀更多精彩內(nèi)容