leetcode95-96 Unique Binary Search Trees I-II

morgan 發布于2019-08-15 11:06 / 1747人閱讀

摘要：在這里我們使用數組中下標為的位置來記錄個元素可以組成的平衡二叉樹的數量。在遞歸的過程中，我們找到以當前節點作為根節點的所有平衡二叉樹，并將結果以形式返回上一級調用。

題目要求

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

返回用1-n這n-1個數字可以構成的全部搜索二叉樹以及其個數。

思路和代碼

如果只是單純的計算二叉樹的數量，其實這就完全轉化成了一道規律題。我們可以從1開始尋找規律。
1： 1
1，2： 12， 21
1，2，3：123，132，213，312，321

我們可以通過dp的方式來記錄。無論以哪一個節點作為root節點，它的左子樹的元素和右子樹的元素都是固定的。也就是說，假設root值為i，那么左子樹的元素為[1...i-1],右子樹的元素為[i+1...n]。因此當前root節點可以生成的平衡二叉樹數量即為左子樹數量*右子樹數量。在這里我們使用int[]數組中下標為n的位置來記錄n個元素可以組成的平衡二叉樹的數量。

    public int numTrees(int n) {
        int[] nums = new int[n+1];
        for(int i = 0 ; i <= n ; i++){
            if(i==0 || i==1) nums[i] = 1;
            else{
                for(int j = 1 ; j<=i ; j++){
                    nums[i] += nums[j-1]*nums[i-j];
                }
            }
        }
        return nums[n];
    }

如果要我們返回具體樹的形態的話，就需要我們通過backtracking的遞歸形式來找到所有的平衡二叉樹。在遞歸的過程中，我們找到以當前節點作為根節點的所有平衡二叉樹，并將結果以list形式返回上一級調用。

    public List generateTrees(int n) {
        if(n==0) return new ArrayList();
        return generateTrees(1,n);
    }
    public List generateTrees(int start, int end){
        List result = new ArrayList();
        if(start>end){
            result.add(null);
        }else if(start==end){
            result.add(new TreeNode(start));
        }else{
            for(int i = start ; i<=end ; i++){
                List left = generateTrees(start, i-1);
                List right = generateTrees(i+1, end);
                for(TreeNode tempLeft : left){
                    for(TreeNode tempRight : right){
                        TreeNode root = new TreeNode(i);
                        root.left = tempLeft;
                        root.right = tempRight;
                        result.add(root);
                    }
                }
            }
            
        }
        return result;
        
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

GPU云服務器云服務器 binary-search binary-search-tree Trees unique

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

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

[LeetCode] 96. Unique Binary Search Trees I &

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

nidaye 2019-08-14 15:22 評論0 收藏0
[Leetcode] Unique Binary Search Trees 唯一二叉搜索樹

摘要：而根可以選擇從到的任意的數，唯一二叉樹的總數，就是根為到的樹相加。所以該問題化簡為以為根，其唯一左子樹和右子樹各有多少，這就是個動態規劃的問題了。 Unique Binary Search Trees I && II 解法請見：https://yanjia.li/zh/2019/02/... Given n, how many structurally unique BSTs (b...

enrecul101 2019-08-14 12:38 評論0 收藏0
leetcode-95-Unique Binary Search Trees II

摘要：題目解讀窮舉列出所有二叉樹的結構類型。重點動態規劃，關注臨近，，之間的關系應用窮舉組合，動態規劃窮舉組合，適用于相鄰元素有規律。處注意邊界值的情況。不能有重復，遺漏。題目解讀：窮舉列出所有二叉樹的結構類型。重點：動態規劃，關注臨近root，left，right之間的關系應用：窮舉組合，動態規劃窮舉組合，適用于相鄰元素有規律。bug處：注意邊界值的情況。不能有重復，遺漏。 clas...

Tony_Zby 2019-07-31 11:11 評論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