leetcode96 不同的二叉搜索树

本文主要是介绍leetcode96 不同的二叉搜索树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

leetcode96 不同的二叉搜索树

题目描述

二叉搜索树

二叉搜索树又称二叉查找树，二叉排序树：
它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。中序遍历二叉搜索树可以得到一个有序序列。
一个无序序列可以通过构造二叉搜索树，然后经过中序遍历得到有序序列。

动态规划

从题目中看出，给定一个有序序列1，2，3…, n求能构造的二叉搜索树的数目。

1. 如果n = 0 或 n = 1，则仅仅能构成一个二叉搜索树；
2. 任取 i 满足1 < i < n， 以 i 为根节点，则左子树为 1,2,…,i -1和右子树 i+1,i+2,…,n均为二叉搜索树，则可以利用递归进行求解。
3. 1,2,3,4 同 5,6,7,8 所构成的二叉搜索树一样多，因为二叉搜索树的构成不关心每一个元素的大小，只是对有序序列的长度敏感。
4. 因此，假设G[n] 表示有序序列1,2,3,…,n的二叉搜索树数目，则有递推公式：

代码实现

public class Solution {public int numTrees(int n){int[] G = new int[n + 1];G[0] = 1;G[1] = 1;for(int i = 2; i <= n; i ++){for(int j = 1; j <= i; j ++){G[i] += G[j - 1] * G[i - j];}}return G[n];}
}

这篇关于leetcode96 不同的二叉搜索树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---