快捷導(dǎo)航

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

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

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

一、題目描述

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

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

二、思路

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

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

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

因此最終結(jié)果為

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

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

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

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

2. 確定遞推公式:

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

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

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

4. 確定遍歷順序:

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

三、代碼

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

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

您可能感興趣的文章: