`

Unique Binary Search Trees II

阅读更多
Given 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

Unique Binary Search Trees 相比这道题目要难一些,要求输出所有可能的二叉查找树。在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> list = new ArrayList<TreeNode>();
        if(n == 0) return list;
        return getGenerate(1, n);
    }
    
    public List<TreeNode> getGenerate(int start, int n) {
        List<TreeNode> list = new ArrayList<TreeNode>();
        if(start > n) {
            list.add(null);
            return list;
        }
        for(int i = start; i <= n; i++) {
            List<TreeNode> left = getGenerate(start, i - 1);
            List<TreeNode> right = getGenerate(i + 1, n);
            for(TreeNode leftNode : left)
                for(TreeNode rightNode: right) {
                    TreeNode root = new TreeNode(i);
                    root.left = leftNode;
                    root.right = rightNode;
                    list.add(root);
                }
        }
        return list;
    }
}
0
0
分享到:
评论

相关推荐

    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 二叉树的递归 ...

    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]...

    陈越、何钦铭-数据结构作业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 ...

    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:力码树

    II 我们可以构造一个递归函数,然后返回BST。我们需要传入的值是一个开始点,一个结束点。递归出口是当开始点大于结束点时返回。我们可以利用BST的性质,也就是左子树的所有值小于根节点,右子树的所有值大于根节点...

    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