# LeetCode Medium 95. Unique Binary Search Trees II

tags: leetcode

問題

• Explore
• Problems

整数$n$が与えられた時, $1 \dots n$を保持する構造的に一意なBST(2分探索木)を生成して, 配列に入れて返せ

[root, root's left, root's right,...]のようにBSTは表示されています

解法

この問題は動的計画法(DP)を用いて解くことも可能らしいですが, まだ理解できていないので単純に再帰的に解いてみることにします

まず, $n=0$のときは空の配列を返します

それ以外の場合について再帰的な関数を用います

深さ

二分木の根から最も遠いノードに行くために必要な最短経路の長さを深さと言います

深さに注目すると$n=3$のときに生成される木を書くことが出来ます

再帰的に解く

最初に根となるノードを定めます

そのノードの左側に来るノード, 右側に来るノードを決めます

これを再帰的に定義すると

• 基底
  • 今のノードが葉であるとき(start > endのとき)は返り値(res)にNULLを追加して返します
  • これは$n$回行われます
• そうでないときは
  • 部分木を付けるノードを決めます(root)
  • そのノードから伸びる左部分木の入った配列(lefts)と右部分木の入った配列(rights)を保持します
  • それぞれの部分木をrootに付けます
  • そして, rootを最終的に返すresに加えます

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        if n == 0:
          return []
        return self.helper(1, n)
        
        
    def helper(self, start, end):
      res = []
      if start > end:
        res.append(None)
        return res
      for i in range(start, end+1):
        lefts = self.helper(start, i-1)
        rights = self.helper(i+1, end)
        for li in range(len(lefts)):
          for ri in range(len(rights)):
            root = TreeNode(i)
            root.left = lefts[li]
            root.right = rights[ri]
            res.append(root)
      return res

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if (n == 0) return {};
        return helper(1, n);
    }
private:
    vector<TreeNode*> helper(int start, int end){
        vector<TreeNode*> res;
        if (start > end) {
            res.push_back(NULL);
            return res;
        }
        for (int i = start; i <= end; i++){
            vector<TreeNode*> lefts = helper(start, i - 1);
            vector<TreeNode*> rights = helper(i + 1, end);
            for (int li = 0; li < (int)lefts.size(); li++){
                for (int ri = 0; ri < (int)rights.size(); ri++){
                    TreeNode* root = new TreeNode(i);
                    root->left = lefts[li];
                    root->right = rights[ri];
                    res.push_back(root);
                }
            }
        }
        return res;
    }
};

Explore

これでRecursion Iは終わりです

次からはRecursioin IIの問題を解いていきます