96. 不同的二叉搜索树

问题96 不同的二叉搜索树

https://leetcode-cn.com/problems/unique-binary-search-trees/

这个题目如果纠结于具体的二叉搜索树形态就想错方向了，关键点是将问题抽象，从整棵树的角度来考虑。我们定义包含从1到n这n个节点的可能的二叉搜索树的个数为S(n)。这些二叉搜索树可能以从1到n的任一个作为根节点，如果以1作为根节点，那么对应的可能的二叉搜索树有多少个呢？因为1是最小值，那么左子树显然是空，右子树包含n-1个节点，所以以1作为根节点，可能的二叉搜索树的个数是1*S(n-1)。同理，以2作为根节点，可能的二叉搜索树的个数是S(1)*S(n-2)。推而广之，以k作为根节点，可能的二叉搜索树的个数是S(k-1)*S(n-k)。所以，包含n个节点的可能的二叉搜索树S(n)=1*S(n-1)+S(1)*S(n-2)+…+S(k-1)*S(n-k)+…+S(n-1)*1。

	public int numTrees(int n) {
		int[] num = new int[n+1];
		num[0] = 1;

		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= i-1; j++) {
				num[i] += num[j] * num[i-1-j];
			}
		}

		return num[n];
	}

在 LeetCode 查看