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

enrecul101 發布于2019-08-14 12:38 / 1009人閱讀

摘要：而根可以選擇從到的任意的數，唯一二叉樹的總數，就是根為到的樹相加。所以該問題化簡為以為根，其唯一左子樹和右子樹各有多少，這就是個動態規劃的問題了。

Unique Binary Search Trees I && II 解法請見：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

動態規劃 復雜度

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

思路

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

代碼

public class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 1;
        //從節點數2開始計算到節點數為n的BST
        for(int i = 2; i < n + 1; i++){
            //計算根是第一個數的BST數量，直到根是最后一個數的BST數量，這里j可以理解為根左邊的節點數
            for(int j = 0; j < i; j++){
                //有n的節點的BST一共有 G(n)=F(1,n-1)+F(2,n-1)+...+F(n-1,n-1)個
                //以i為根總共n個節點的BST有 F(i,n)=G(i-1)*G(i+1->n)個
                //BST形態數量之和一共有多少個節點有關 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];
    }
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64611.html

leetcode95-96 Unique Binary Search Trees I-II

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

morgan 2019-08-15 11:06 評論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 2019-08-16 10:27 評論0 收藏0
前端 | 每天一個 LeetCode

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

張漢慶 2019-08-23 13:42 評論0 收藏0
[Leetcode] Validate Binary Search Tree 驗證二叉搜索樹

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

fuchenxuan 2019-08-14 12:40 評論0 收藏0
LeetCode 之 JavaScript 解答第98題 —— 驗證二叉搜索樹

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

用戶84 2019-08-23 17:12 評論0 收藏0