Unique Binary Search Trees II Java

最新推荐文章于 2020-04-13 21:17:20 发布

Spencer_Lin

最新推荐文章于 2020-04-13 21:17:20 发布

阅读量552

点赞数

分类专栏： LeetCode BinaryTree+BSF+DFS 文章标签： leetcode recursion

本文链接：https://blog.csdn.net/linxiang0591/article/details/38872665

版权

LeetCode BinaryTree+BSF+DFS 专栏收录该内容

16 篇文章

订阅专栏

本文提供了一种使用递归循环方法生成从1到n的所有唯一二叉搜索树的方法，包括理解复杂参数如'{1,#,2,3}

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

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

confused what "{1,#,2,3}" means?

This problem is belong to NP-Problem Category,
And similar idea of N-Queues problem
solve by Loop-Recursion method
Idea:
1. Recursion for nodes of leftList and rightList
leftList=(left,i-1), rightList=(i+1,right)
2. Use Nested Loop with depth 2
set (i as root)，
3. connect left and right one by one
nested Loop index j(leftList) and k(rightList)
4. Finally, add root into result list

public class Solution {
    public List<TreeNode> generateTrees(int n) {
     return helper(1,n);
    }
    private ArrayList<TreeNode> helper(int left, int right){
        ArrayList<TreeNode> res=new ArrayList<TreeNode>();
        //base case
        if(left>right){
            res.add(null);
        }
        //recursion case
        for(int i=left;i<=right;i++) {
            ArrayList<TreeNode> leftList = helper(left, i - 1);
            ArrayList<TreeNode> rightList = helper(i+1,right);
            //gernate tree from leftList and rightList;
            for(int j=0;j<leftList.size();j++){
                for(int k=0;k<rightList.size();k++){
                    TreeNode root=new TreeNode(i);
                    root.left=leftList.get(j);
                    root.right=rightList.get(k);
                    res.add(root);
                }
            }
        }
        return res;
    }
}