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;
    }
    
}