專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專欄：50多種經(jīng)典圖論算法全部掌握

一網(wǎng)友冷嘲熱諷的發(fā)文稱：原來(lái)小紅書還在大小周啊，真可憐。其中一位小紅書的員工回到：不用可憐，雙倍工資，盼著每周多加幾天呢。如果周末加班真的是雙倍工資，確實(shí)很良心了，估計(jì)也會(huì)有不少人盼著周末加班。

在互聯(lián)網(wǎng)行業(yè)周末加班還給工資的確實(shí)不多，我之前工作過(guò)的一些公司無(wú)論是工作日加班還是周末加班，都會(huì)記錄加班時(shí)長(zhǎng)，可以用來(lái)調(diào)休，從來(lái)不會(huì)算到工資上的，到最后裁員的時(shí)候，如果沒(méi)有調(diào)休完，有的會(huì)給你折算成賠償，有的直接不算，等于白加了，能把加班折算成雙倍工資的真的不多見。

--------------下面是今天的算法題--------------

來(lái)看下今天的算法題，這題是LeetCode的第95. 不同的二叉搜索樹 II。

問(wèn)題描述

來(lái)源：LeetCode第95題

難度：中等

給你一個(gè)整數(shù) n ，請(qǐng)你生成并返回所有由 n 個(gè)節(jié)點(diǎn)組成且節(jié)點(diǎn)值從 1 到 n 互不相同的不同二叉搜索樹 。可以按任意順序返回答案。

示例1：

輸入：n = 3 輸出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

示例2：

輸入：n = 1 輸出：[[1]]

• 1 <= n <= 8

問(wèn)題分析

這題讓用 n 個(gè)整數(shù)構(gòu)成不同的二叉搜索樹，關(guān)于二叉搜索樹的更多知識(shí)可以看下前面講的。因?yàn)槎嫠阉鳂渥笞訕渖系乃泄?jié)點(diǎn)都小于根節(jié)點(diǎn)，右子樹上的所有節(jié)點(diǎn)都大于根節(jié)點(diǎn)。

我們可以選擇任何一個(gè)數(shù)字把它當(dāng)做根節(jié)點(diǎn)，它左邊的所有數(shù)字構(gòu)成左子樹，右邊的所有數(shù)字構(gòu)成右子樹。比如 n 等于 8 ，我們可以選擇 3 作為根節(jié)點(diǎn)，左邊的所有數(shù)字[1,2]構(gòu)成左子樹，右邊的所有數(shù)字[4,5,6,7,8]構(gòu)成右子樹。這里除了選擇 3 以外我們還可以選擇任何其他數(shù)字當(dāng)做根節(jié)點(diǎn)，只需要枚舉即可。

然后左子樹和右子樹的構(gòu)建可以使用同樣的方式，所以這是一個(gè) 分治算法 。先通過(guò)枚舉的方式確定根節(jié)點(diǎn)，然后通過(guò)遞歸的方式創(chuàng)建左右子樹，因?yàn)樽笞訕浜陀易訕淇赡苡卸鄠€(gè)，所以要通過(guò)自由組合的方式來(lái)創(chuàng)建該二叉樹。

JAVA：

public List   generateTrees (int n)  {
    return generateTrees(1, n);
}

// 左閉右閉區(qū)間[start,end]
public List   generateTrees (int start, int end)  {
    List
       
  mList =  new ArrayList<>();      if (start > end) { // 無(wú)效區(qū)間         mList.add( null);          return mList;     }      // 區(qū)間繼續(xù)分成三部分，其中[i]是當(dāng)前節(jié)點(diǎn)，[start, i - 1]是當(dāng)前節(jié)點(diǎn)的所有      // 左子節(jié)點(diǎn)，[i + 1, end]是當(dāng)前節(jié)點(diǎn)的所有右子節(jié)點(diǎn)，左右子節(jié)點(diǎn)繼續(xù)遞歸創(chuàng)建。      for ( int i = start; i <= end; i++) {          // 遞歸創(chuàng)建左子樹         List  leftTrees = generateTrees(start, i -  1);          // 遞歸創(chuàng)建右子樹         List  rightTrees = generateTrees(i +  1, end);          // 從左子樹集合中選出一棵左子樹，從右子樹集合中選出一棵右子樹，拼接到根節(jié)點(diǎn)上          for (TreeNode left : leftTrees) {              for (TreeNode right : rightTrees) {                 TreeNode curTree =  new TreeNode(i); // 創(chuàng)建當(dāng)前節(jié)點(diǎn)                 curTree.left = left;                 curTree.right = right;                 mList.add(curTree); // 構(gòu)造一顆新的樹添加到集合中。             }         }     }      return mList; }

C++：

public:
    vector   generateTrees (int n)  {
        return generateTrees(1, n);
    }

    // 左閉右閉區(qū)間[start,end]
    vector   generateTrees (int start, int end)  {
        vector
       
  vec;          if (start > end) { // 無(wú)效區(qū)間             vec.push_back( nullptr);              return vec;         }          // 區(qū)間繼續(xù)分成三部分，其中[i]是當(dāng)前節(jié)點(diǎn)，[start, i - 1]是當(dāng)前節(jié)點(diǎn)的所有          // 左子節(jié)點(diǎn)，[i + 1, end]是當(dāng)前節(jié)點(diǎn)的所有右子節(jié)點(diǎn)，左右子節(jié)點(diǎn)繼續(xù)遞歸創(chuàng)建。          for ( int i = start; i <= end; i++) {              // 遞歸創(chuàng)建左子樹              vector  leftTrees = generateTrees(start, i -  1);              // 遞歸創(chuàng)建右子樹              vector  rightTrees = generateTrees(i +  1, end);              // 從左子樹集合中選出一棵左子樹，從右子樹集合中選出一棵右子樹，拼接到根節(jié)點(diǎn)上              for (TreeNode *left: leftTrees) {                  for (TreeNode *right: rightTrees) {                      auto *curTree =  new TreeNode(i); // 創(chuàng)建當(dāng)前節(jié)點(diǎn)                     curTree->left = left;                     curTree->right = right;                     vec.emplace_back(curTree); // 構(gòu)造一顆新的樹添加到集合中。                 }             }         }          return vec;     }

Python：

def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
    def generateTrees(start, end):  # 左閉右閉區(qū)間[start,end]
        trees = []
        if start > end:  # 無(wú)效區(qū)間
            trees.append(None)
            return trees
        # 區(qū)間繼續(xù)分成三部分，其中[i]是當(dāng)前節(jié)點(diǎn)，[start, i - 1]是當(dāng)前節(jié)點(diǎn)的所有
        # 左子節(jié)點(diǎn)，[i + 1, end]是當(dāng)前節(jié)點(diǎn)的所有右子節(jié)點(diǎn)，左右子節(jié)點(diǎn)繼續(xù)遞歸創(chuàng)建。
        for i in range(start, end + 1):
            left_trees = generateTrees(start, i - 1)  # 遞歸創(chuàng)建左子樹
            right_trees = generateTrees(i + 1, end)  # 遞歸創(chuàng)建右子樹
            # 從左子樹集合中選出一棵左子樹，從右子樹集合中選出一棵右子樹，拼接到根節(jié)點(diǎn)上
            for left in left_trees:
                for right in right_trees:
                    node = TreeNode(i)  # 創(chuàng)建當(dāng)前節(jié)點(diǎn)
                    node.left = left
                    node.right = right
                    trees.append(node)  # 構(gòu)造一顆新的樹添加到集合中。
        return trees

    return generateTrees(1, n)

筆者簡(jiǎn)介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個(gè)算法網(wǎng)站中累計(jì)做題2000多道，在公眾號(hào)中寫算法題解800多題，對(duì)算法題有自己獨(dú)特的解題思路和解題技巧，喜歡的可以給個(gè)關(guān)注，也可以 下載我整理的1000多頁(yè)的PDF算法文檔 。