`

Unique Binary Search Trees 总结

阅读更多
有关unique 二叉搜索树的题目有两个,第一道题目是确定二叉搜索树的个数,第二道题目是输出所有的二叉搜索树,这两道题目属于比较难的题目,对于解决它们的方法也是比较重要的,我们要掌握。

1,Unique Binary Search Trees
给定一个正整数n,确定有多少个不同的二叉搜索树,树的节点取值范围为(1....n)。
例如:给定n = 3,输出为5
   1           3     3      2       1
     \         /     /        / \        \
      3     2     1       1  3       2
     /      /        \                      \
   2      1          2                     3

求解这个问题我们不妨从简单开始分析,我们设定一个数组result来表示n在不同值下有几种不同的二叉树。当n为0时,这时是一颗空树,result[0] = 1; 当n = 1时,只有一种情况,result[1] = 1; 当n = 2 时,两个数可以分别作为根节点,result[2] = 2; 当n = 3时,正如题目给出的结果,result[3] = 5;我们从这里可以发现一些规律,result[n] = result[0] * result[n - 1] + result[1] * result[n -2] + result[n-1] * result[0] (n > 1); 我们会发现这正好符合卡特兰数的递推式,有了递推式我们就很容易的写出代码了,代码如下:
public class Solution {
    public int numTrees(int n) {
        int[] result = new int[n+1];
        result[0] = 1;
        result[1] = 1;
        for(int i = 2; i <= n; i++)
            for(int j = 0; j < i; j++) {
                result[i] += result[j] * result[i-j-1];
            }
        return result[n];
    }
}


2,Unique Binary Search Trees II
给定一个正整数n,输出所有不同的二叉搜索树,数的节点取值范围为(1....n)。
例如:给定n = 3
   1           3     3      2       1
     \         /     /        / \        \
      3     2     1       1  3       2
     /      /        \                      \
   2      1          2                     3
输出:[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

这道题目比上一道题目要难,要输出所有不同的二叉搜索树,解决树的问题我们首先想到的就是用递归来解决,对于这道题目,我们参考之前介绍过的一道题目Different Ways to Add Parentheses,我们同样在for循环中递归解决子问题,这个方法需要我们通过题目来巩固,代码如下:
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> result = new ArrayList<TreeNode>();
        if(n == 0) return result;
        return generateSubtrees(1, n);
    }
    
    public List<TreeNode> generateSubtrees(int start, int n) {
        List<TreeNode> result = new ArrayList<TreeNode>();
        if(start > n) {
            result.add(null);
            return result;
        }
        for(int i = start; i <= n; i++) {
            List<TreeNode> left = generateSubtrees(start, i - 1);
            List<TreeNode> right = generateSubtrees(i + 1, n);
            for(TreeNode leftnode : left)
                for(TreeNode rightnode : right) {
                    TreeNode root = new TreeNode(i);
                    root.left = leftnode;
                    root.right = rightnode;
                    result.add(root);
                }
        }
        return result;
    }
}



分享到:
评论

相关推荐

    陈越、何钦铭-数据结构作业16:Complete Binary Search Tree完全二叉搜索树

    Both the left and right subtrees must also be binary search trees. A Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled ...

    CBST.rar_The Keys_bst

    Both the left and right subtrees must also be binary search trees. A Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled ...

    cpp-算法精粹

    Unique Binary Search Trees II Validate Binary Search Tree Convert Sorted Array to Binary Search Tree Convert Sorted List to Binary Search Tree LCA of BST Kth Smallest Element in a BST 二叉树的递归 ...

    leetcodepython001-Algorithm:关于数据结构和算法的问题(Leetcode、编程之美和课程作业)

    leetcode python 001 Algorithm 用python和java解决了Leetcode上部分问题,另外还有对常规算法和机器学习算法的一些实现,例如用遗传算法解物流配送问题。...Search Trees Python 2017/11/28 Medium 09

    leetcode卡-leetcode:Python

    leetcode卡 leetcode 自己刷leetcode,然后记录下来。。。相当于打卡吧! (Unique Binary Search Trees需要用)

    leetcode答案-LeetCodeSolution:这是LeetCode网站问题的解决方案集

    Unique Binary Search Trees 本题参考了 里面的*How Many Binary Trees Are There?*章节。 The first few terms: C(0) = 1 C(1) = C(0)C(0) = 1 C(2) = C(0)C(1) + C(1)C(0) = 2 C(3) = C(0)C(2) + C(1)C(1)

    leetcode添加元素使和等于-Leetcode-tree:力码树

    leetcode添加元素使和等于 Leetcode-tree 94题 Binary ...Search Trees 这道题我们使用了动态规划的方法。说到动态规划我们这里先总结一下动态规划类型的题该如何做。 动态规划题目特点: 计数型: -有

    LeetCode最全代码

    * [Binary Search Tree](https://github.com/kamyu104/LeetCode#binary-search-tree) * [Breadth-First Search](https://github.com/kamyu104/LeetCode#breadth-first-search) * [Depth-First Search]...

    leetcode1477-coding-for-fun:编码乐趣

    96.unique-binary-search-trees.cpp [TODO] 70. 爬楼梯.cpp [TODO] 746. min-cost-climbing-stairs.cpp 第 4 天: [待办事项] leetcode/1143。 最长公共子序列.cpp 第 5 天: [待办事项] leetcode/221。 最大平方....

    EhLib 6.3 Build 6.3.176 Russian version. Full source included.

    Allows keep record in the manner of trees. Each record can have record elements-branches and itself be an element to other parental record. Component TDBGridEh supports to show the tree-type ...

    EhLib 8.0 Build 8.0.023 Pro Edition FullSource for D7-XE8

    Allows keep record in the manner of trees. Each record can have record elements-branches and itself be an element to other parental record. Component TDBGridEh supports to show the tree-type ...

    ehlib_vcl_src_9_3.26

    Allows keep record in the manner of trees. Each record can have record elements-branches and itself be an element to other parental record. Component TDBGridEh supports to show the tree-type ...

    EhLib 9.1.024

    Allows keep record in the manner of trees. Each record can have record elements-branches and itself be an element to other parental record. Component TDBGridEh supports to show the tree-type ...

    python3.6.5参考手册 chm

    Python参考手册,官方正式版参考手册,chm版。以下摘取部分内容:Navigation index modules | next | Python » 3.6.5 Documentation » Python Documentation contents What’s New in Python ...

Global site tag (gtag.js) - Google Analytics