快捷導(dǎo)航

Java動(dòng)態(tài)規(guī)劃方式解決不同的二叉搜索樹

更新時(shí)間：2022年10月21日 09:17:20 作者：劉婉晴

二叉搜索樹作為一個(gè)經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，具有鏈表的快速插入與刪除的特點(diǎn)，同時(shí)查詢效率也很優(yōu)秀，所以應(yīng)用十分廣泛。本文將詳細(xì)講講二叉搜索樹的原理與實(shí)現(xiàn)，需要的可以參考一下

一、題目描述

給你一個(gè)整數(shù) n ，求恰由 n 個(gè)節(jié)點(diǎn)組成且節(jié)點(diǎn)值從 1 到 n 互不相同的二叉搜索樹有多少種？返回滿足題意的二叉搜索樹的種數(shù)。

來(lái)源：https://leetcode.cn/problems/unique-binary-search-trees/

二、思路

本題可以使用動(dòng)態(tài)規(guī)劃的方式解決，我們先來(lái)看一下大題思路。以 n = 3 為例，n = 3 時(shí)的不同的二叉搜索樹數(shù)目，可以通過(guò)分別以 1 為根節(jié)點(diǎn)，以 2 為根節(jié)點(diǎn)，以 3 為根節(jié)點(diǎn) 的不同的二叉搜索樹的數(shù)量加和獲得。

那么問(wèn)題就來(lái)到了如何得到以 1 為根節(jié)點(diǎn)，以 2 為根節(jié)點(diǎn)，以 3 為根節(jié)點(diǎn) 的不同二叉搜索樹數(shù)量。這就是我們動(dòng)態(tài)規(guī)劃，主要處理的問(wèn)題。

以 1 為根節(jié)點(diǎn) 時(shí)：此時(shí)其左子樹具有 dp[1-1] 種選擇（左子樹無(wú)節(jié)點(diǎn)），右子樹具有 dp[3-1] 種選擇（節(jié)點(diǎn) 2，3）
以 2 為根節(jié)點(diǎn) 時(shí)：此時(shí)其左子樹具有 dp[2-1] 種選擇（節(jié)點(diǎn) 1），右子樹具有 dp[3-2] 種選擇（節(jié)點(diǎn) 3）
以 3 為根節(jié)點(diǎn)時(shí)：此時(shí)其左子樹具有 dp[3-1] 種選擇（節(jié)點(diǎn) 1，2），右子樹具有 dp[3-3] 中選擇（右子樹無(wú)節(jié)點(diǎn)）

因此最終結(jié)果為

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

分析完了 n = 3 的情況，下面我們來(lái)看一下一般情況：

1. dp數(shù)組以及下標(biāo)的含義:

dp[] 數(shù)組表示二叉搜索樹數(shù)量，下標(biāo) i 表示當(dāng) n = i 時(shí)，所含的二叉搜索樹數(shù)量

2. 確定遞推公式:

dp[i] += dp[i-1] * dp[i-j] (其中 1<=j<=i, 表示以 j 為根節(jié)點(diǎn)的二叉搜索樹)

3. dp數(shù)組如何初始化

當(dāng)二叉樹一個(gè)節(jié)點(diǎn)都沒有，即 dp[0] 時(shí) ，二叉搜索樹只有一種情況 dp[0] = 1
當(dāng)二叉樹只有一個(gè)節(jié)點(diǎn)時(shí)，即 dp[1] 時(shí)，二叉搜索樹只有一種情況 dp[1] = 1

4. 確定遍歷順序:

節(jié)點(diǎn)數(shù)為 3 的二叉搜索樹種類數(shù)，需要用節(jié)點(diǎn)數(shù)為 2 的二叉搜索樹推出，因此順序遍歷從 3 ~ n 即可

三、代碼

    // 不同的二叉搜索樹
    public int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1; // 初始化動(dòng)態(tài)規(guī)劃數(shù)組
        for(int i=2; i<n+1; i++){
            for(int j=1; j<=i; j++){ // 分別以 1 ~ i 為根節(jié)點(diǎn)，計(jì)算二叉樹種類數(shù)，累加到結(jié)果中
                dp[i] += dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }

到此這篇關(guān)于Java動(dòng)態(tài)規(guī)劃方式解決不同的二叉搜索樹的文章就介紹到這了,更多相關(guān)Java二叉搜索樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: