成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] Unique Binary Search Trees 唯一二叉搜索樹

enrecul101 / 1022人閱讀

摘要：而根可以選擇從到的任意的數(shù)，唯一二叉樹的總數(shù)，就是根為到的樹相加。所以該問(wèn)題化簡(jiǎn)為以為根，其唯一左子樹和右子樹各有多少，這就是個(gè)動(dòng)態(tài)規(guī)劃的問(wèn)題了。

Unique Binary Search Trees I && II 解法請(qǐng)見：https://yanjia.li/zh/2019/02/... 
Given n, how many structurally unique BST"s (binary search trees) that store values 1...n?


For example, Given n = 3, there are a total of 5 unique BST"s.


   1         3     3      2      1
           /     /      /       
     3     2     1      1   3      2
    /     /                        
   2     1         2                 3
動(dòng)態(tài)規(guī)劃 復(fù)雜度

時(shí)間 O(N!) 空間 O(N)

思路

二叉搜索樹有個(gè)性質(zhì)，就是左邊的數(shù)都比根小，右邊的數(shù)都比根大。另外，題目說(shuō)明二叉樹的節(jié)點(diǎn)是從1到n，所以我們能確定如果根為k，則根左邊的數(shù)是1到k-1，根右邊的數(shù)是k+1到n。還有一點(diǎn)技巧是，對(duì)于通過(guò)一個(gè)根來(lái)說(shuō)，唯一二叉樹的數(shù)量是其左子樹的數(shù)量乘以右子樹的數(shù)量，這是簡(jiǎn)單的乘法原理。并且，左右子樹的形態(tài)數(shù)量是跟具體的數(shù)無(wú)關(guān)的，只跟這個(gè)樹里有多少節(jié)點(diǎn)有關(guān)。而根可以選擇從1到n的任意的數(shù)，唯一二叉樹的總數(shù)，就是根為1到n的樹相加。所以該問(wèn)題化簡(jiǎn)為以k為根，其唯一左子樹和右子樹各有多少，這就是個(gè)動(dòng)態(tài)規(guī)劃的問(wèn)題了。我們建立一個(gè)數(shù)組dp[i]，代表節(jié)點(diǎn)數(shù)為i的唯一子樹有多少個(gè)。顯然dp[0]=dp[1]=1。

代碼 
public class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 1;
        //從節(jié)點(diǎn)數(shù)2開始計(jì)算到節(jié)點(diǎn)數(shù)為n的BST
        for(int i = 2; i < n + 1; i++){
            //計(jì)算根是第一個(gè)數(shù)的BST數(shù)量，直到根是最后一個(gè)數(shù)的BST數(shù)量，這里j可以理解為根左邊的節(jié)點(diǎn)數(shù)
            for(int j = 0; j < i; j++){
                //有n的節(jié)點(diǎn)的BST一共有 G(n)=F(1,n-1)+F(2,n-1)+...+F(n-1,n-1)個(gè)
                //以i為根總共n個(gè)節(jié)點(diǎn)的BST有 F(i,n)=G(i-1)*G(i+1->n)個(gè)
                //BST形態(tài)數(shù)量之和一共有多少個(gè)節(jié)點(diǎn)有關(guān) G(i+1->n)=G(n-i)
                //所以G(n)= G(0)*G(n-1)+G(1)*G(n-2)+...
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        return dp[n];
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64611.html

相關(guān)文章

  • leetcode95-96 Unique Binary Search Trees I-II

    摘要：在這里我們使用數(shù)組中下標(biāo)為的位置來(lái)記錄個(gè)元素可以組成的平衡二叉樹的數(shù)量。在遞歸的過(guò)程中，我們找到以當(dāng)前節(jié)點(diǎn)作為根節(jié)點(diǎn)的所有平衡二叉樹，并將結(jié)果以形式返回上一級(jí)調(diào)用。 題目要求 Given n, how many structurally unique BSTs (binary search trees) that store values 1...n? For example, Gi...

    morgan 評(píng)論0 收藏0

  • [Leetcode-Dynamic Programming]Unique Binary Search

    Unique Binary Search TreesGiven n, how many structurally unique BSTs (binary search trees) that store values 1...n? For example,Given n = 3, there are a total of 5 unique BSTs. 1 3 3 ...

    MartinDai 評(píng)論0 收藏0

  • 前端 | 每天一個(gè) LeetCode

    摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...

    張漢慶 評(píng)論0 收藏0

  • [Leetcode] Validate Binary Search Tree 驗(yàn)證二叉搜索樹

    摘要：注意這里的結(jié)構(gòu)和不同的二叉樹遍歷一樣，如果到空節(jié)點(diǎn)就返回，否則遞歸遍歷左節(jié)點(diǎn)和右節(jié)點(diǎn)。唯一不同是加入了和，所以要在遞歸之前先判斷是否符合和的條件。代碼如果該節(jié)點(diǎn)大于上限返回假如果該節(jié)點(diǎn)小于下限返回假遞歸判斷左子樹和右子樹 Validate Binary Search Tree Given a binary tree, determine if it is a valid binary...

    fuchenxuan 評(píng)論0 收藏0

  • LeetCode 之 JavaScript 解答第98題 —— 驗(yàn)證二叉搜索樹

    摘要：小鹿題目驗(yàn)證二叉搜索樹給定一個(gè)二叉樹，判斷其是否是一個(gè)有效的二叉搜索樹。假設(shè)一個(gè)二叉搜索樹具有如下特征節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。所有左子樹和右子樹自身必須也是二叉搜索樹。算法思路定義全局的變量，用來(lái)返回是否為二叉搜索樹。 Time：2019/4/24Title: Vaildata Binary Search TreeDifficulty: MediumAuthor: 小鹿 ...

    用戶84 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<