位置：首页>> 软件编程>> java编程>> Java动态规划方式解决不同的二叉搜索树

Java动态规划方式解决不同的二叉搜索树

作者：刘婉晴　　发布时间：2023-03-02 01:56:52　

标签：Java,动态规划,二叉搜索树

一、题目描述

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。

来源：https://leetcode.cn/problems/unique-binary-search-trees/

二、思路

本题可以使用动态规划的方式解决，我们先来看一下大题思路。以 n = 3 为例，n = 3 时的不同的二叉搜索树数目，可以通过分别以 1 为根节点，以 2 为根节点，以 3 为根节点的不同的二叉搜索树的数量加和获得。

那么问题就来到了如何得到以 1 为根节点，以 2 为根节点，以 3 为根节点的不同二叉搜索树数量。这就是我们动态规划，主要处理的问题。

以 1 为根节点时：此时其左子树具有 dp[1-1] 种选择（左子树无节点），右子树具有 dp[3-1] 种选择（节点 2，3）
以 2 为根节点时：此时其左子树具有 dp[2-1] 种选择（节点 1），右子树具有 dp[3-2] 种选择（节点 3）
以 3 为根节点时：此时其左子树具有 dp[3-1] 种选择（节点 1，2），右子树具有 dp[3-3] 中选择（右子树无节点）

因此最终结果为

dp[1-1] * dp[3-1] + dp[2-1] * dp[3-2] + dp[3-1] * dp[3-3]

分析完了 n = 3 的情况，下面我们来看一下一般情况：

1. dp数组以及下标的含义:

dp[] 数组表示二叉搜索树数量，下标 i 表示当 n = i 时，所含的二叉搜索树数量

2. 确定递推公式:

dp[i] += dp[i-1] * dp[i-j] (其中 1<=j<=i, 表示以 j 为根节点的二叉搜索树)

3. dp数组如何初始化

当二叉树一个节点都没有，即 dp[0] 时，二叉搜索树只有一种情况 dp[0] = 1
当二叉树只有一个节点时，即 dp[1] 时，二叉搜索树只有一种情况 dp[1] = 1

4. 确定遍历顺序:

节点数为 3 的二叉搜索树种类数，需要用节点数为 2 的二叉搜索树推出，因此顺序遍历从 3 ~ n 即可

三、代码

// 不同的二叉搜索树
public int numTrees(int n) {
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = 1; // 初始化动态规划数组
for(int i=2; i<n+1; i++){
for(int j=1; j<=i; j++){ // 分别以 1 ~ i 为根节点，计算二叉树种类数，累加到结果中
dp[i] += dp[j-1]*dp[i-j];
}
}
return dp[n];
}

来源：https://blog.csdn.net/liuwanqing233333/article/details/127298750

投稿

Java动态规划方式解决不同的二叉搜索树

一、题目描述

二、思路

三、代码

猜你喜欢