一、題目描述

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

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

二、思路

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

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

• 以 1 為根節(jié)點(diǎn) 時(shí)： 此時(shí)其左子樹具有 dp[1-1] 種選擇（左子樹無節(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] 中選擇（右子樹無節(jié)點(diǎn)）

因此 最終結(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í)，所含的二叉搜索樹數(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)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論