By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、不同的二叉搜索树1

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

示例:

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

1.1、解题思路

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

它的左、右子树也分别为二叉排序树。

1、假设n个节点存在二叉排序树的个数是G(n)，令f(i)为以i为根的二叉搜索树的个数，则

G(n)=f(1)+f(2)+f(3)+f(4)+...+f(n)

2、根据连续的数组成的二叉搜索树的特点，当i为根节点时，其左子树节点个数为i-1个，右子树节点为n-i， 则f(i)=G(i−1)∗G(n−i)

n G(n)
0 1
1 1
2 G(2)=G(0)∗G(1)+G(1)∗G(0)
3 G(3)=G(0)∗G(2)+G(1)∗G(1)+G(2)∗G(0)
n G(n)=G(0)∗G(n−1)+G(1)∗G(n−2)+…+G(n−1)∗G(0)

1.2、算法

/**
* 所求即为：G（n）
*/
public int numTrees(int n) {
    int[] dp = new int[n+1];
    //空数最为第一个，而且下面要用，所以上面的数组个数为n+1
    dp[0] = 1;
    dp[1] = 1;

    // j 为有多少个数字要组成二叉搜索树
    //j = 0 和 j - 1 提前给出来了，所以j从2开始计算，
    for(int j = 2; j <= n; j++) {
        //i 为当前跟节点 ,该循环相当于就是将, j个数字都作为节点的时相加就是 dp[j]
        for(int i = 1; i <= j; i++) {
            dp[j] += dp[i-1] * dp[j-i];
        }
    }
    return dp[n];
}

1.3、测试

@Test
public void test(){

    System.out.println(numTrees(3));
}

2、不同的二叉搜索树_2

给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。

示例：

输入：3
输出：
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释：
以上的输出对应以下 5 种不同结构的二叉搜索树：

1         3     3      2      1
\       /     /      / \      \
3     2     1      1   3      2
/     /       \                 \
2     1         2                 3

1.1、解题思路

其实和 1 还是有些类似，具体看代码吧

1.2、算法

public List<TreeNode> generateTrees(int n) {
    if (n == 0) {
        return new ArrayList<>();
    }
    return generateTrees(1, n);
}


/**
     * 获取 从 start 到 end 所有二叉树的集合
     */
public List<TreeNode> generateTrees(int start, int end) {
    List<TreeNode> list = new ArrayList<>();
    // 当前二叉搜索树为空，（因为我们要打印 null，所以需要 list.add(null) ）返回空节点即可。
    if (start > end) {
        list.add(null);
        return list;
    }

    // 遍历所有的节点
    for (int i = start; i <= end; i++) {
        // 获得 以 i 为跟节点 所有的左子树集合
        List<TreeNode> leftList = generateTrees(start, i - 1);

        // 获得 以 i 为跟节点 所有的右子树集合
        List<TreeNode> rightList = generateTrees(i + 1, end);


        // 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
        for (TreeNode left : leftList) {
            for (TreeNode right : rightList) {
                TreeNode node = new TreeNode(i);
                node.left = left;
                node.right = right;
                list.add(node);
            }
        }
    }
    return list;
}

1.3、测试

    @Test
    public void test(){
        System.out.println(generateTrees(3));
    }


    public TreeNode initTreeNode(){
        TreeNode treeNode1 = new TreeNode(3, null ,null);
        TreeNode treeNode2 = new TreeNode(6, null , null);
        TreeNode treeNode3 = new TreeNode(4, treeNode1, treeNode2);
        TreeNode treeNode4 = new TreeNode(1, null, null);
        TreeNode root = new TreeNode(5, treeNode3, treeNode4);
        return root ;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
        TreeNode(int x, TreeNode left, TreeNode right) {
            this.val = x;
            this.left = left;
            this.right = right;

        }
    }

​

ContactAuthor