leetcode:Unique Binary Search Trees II

问题描述：

Given an integer 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
      

原问题链接：https://leetcode.com/problems/unique-binary-search-trees-ii/

问题分析

递归法

　　这个问题在之前的讨论里已经列出了它的基本递归属性。对于给定的n个元素来说，它构成的子树数量是类似于如下的关系：f(n) = sum(f(i) * f(n - i - 1)) (i = 1, ... n)

　　在这里，就是需要将这个描述的递归关系转化成代码。从实现细节的角度来说，我们这里定义一个generateTree(int start, int end) 的递归函数。start, end分别表示构造树的起始数和结尾数。在start > end的时候，我们返回null作为它的结果集。否则的情况下针对(start, i - 1) (i + 1, end)来递归的构造以i节点为根的数，并将根节点加入到结果集中。

　　详细的代码实现如下：

/**
 * 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) {
        if(n == 0) return new ArrayList<TreeNode>();
        return generateTrees(1, n);
    }

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

动态规划法

 　　除了上述的递归法，我们也可以利用前面递归的条件来用动态规划法来做。主要的思路也近似，就是用一个List[]数组或者列表来保存前面的结果，针对0个元素返回一个空的list。

　　详细的代码实现如下：

/**
 * 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) {
        if(n == 0) return new ArrayList<TreeNode>();
        List<TreeNode>[] list = new List[n + 1];
        list[0] = new ArrayList<>();
        list[0].add(null);
        for(int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
            for(int j = 0; j < i; j++) {
                for(TreeNode lNode: list[j])
                    for(TreeNode rNode : list[i - j - 1]) {
                        TreeNode node = new TreeNode(j + 1);
                        node.left = lNode;
                        node.right = clone(rNode, j + 1);
                        list[i].add(node);
                    }
            }
        }
        return list[n];
    }
    
    private TreeNode clone(TreeNode node, int offset) {
        if(node == null) return null;
        TreeNode cloneNode = new TreeNode(node.val + offset);
        cloneNode.left = clone(node.left, offset);
        cloneNode.right = clone(node.right, offset);
        return cloneNode;
    }
    
}