LeetCode 95. Unique Binary Search Trees II

发布时间：2020-12-14 04:36:14 所属栏目：大数据来源：网络整理

导读：Problem Description: Given an integer? n ,generate all structurally unique?BST‘s?(binary search trees) that store values 1 ...? n . ?给定一个整数n，生成所有不同的二叉搜索树，其节点存储所有从1到n的值。此题是96题的follow up，96题采用动态规

Problem Description:

Given an integer?n,generate all structurally unique?BST‘s?(binary search trees) that store values 1 ...?n.

?给定一个整数n，生成所有不同的二叉搜索树，其节点存储所有从1到n的值。

此题是96题的follow up，96题采用动态规划顺利接出来了，但是看到这个题时没有想到如何利用96题的动态规划的思路（没有想到clone的方法），碰壁了几次。

想到过按顺序插入值到二叉树中，但是这样会出现重复，例如n=3，按2，1，3和按2，3，1插入顺序会得到相同的结果，且重复问题难以解决。

可行的解法有递归的解法和动态规划（参考了huahuajiang的的博客https://zxi.mytechroad.com/blog/uncategorized/leetcode-95-unique-binary-search-trees-ii/）。

def gen(s,e):
  return [tree(i,l,r) for l in gen(s,i – 1) for r in gen(i + 1,e) for i in range(s,e+1)

时间复杂度O(n^3) 空间复杂度 O(n^3)

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

要注意这个终止条件，if(start > end)，这个仅仅当循环中i=start或i=end时才会发生，且start最多比end大于1。

然后是动态规划

class Solution {
    public List<TreeNode> generateTrees(int n) {
        if(n == 0) return new ArrayList<>();
        List<TreeNode>[] dp = new ArrayList[n + 1];
        dp[0] = new ArrayList<>();
        dp[0].add(null);
        for(int i = 1; i <= n; i++) {
            dp[i] = new ArrayList<>();
            for(int j = 0; j < i; j++) {
                for(TreeNode left : dp[j]) {
                    for(TreeNode right : dp[i - j - 1]) {
                        TreeNode root = new TreeNode(j + 1);
                        root.left = left;
                        root.right = clone(right,j + 1);
                        dp[i].add(root);
                    }
                }
            }
        }
        return dp[n];
    }
    public TreeNode clone(TreeNode root,int offset) {
        if(root == null) return root;
        TreeNode newRoot = new TreeNode(root.val + offset);
        newRoot.left = clone(root.left,offset);
        newRoot.right = clone(root.right,offset);
        return newRoot;
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!