[LeetCode] 95. Unique Binary Search Trees II

轉自LeetCode

Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

<Solution>

這題是 Unique Binary Search Tree 的衍生題

這題的觀念也可以用在 241. Different Ways to Add Parentheses

這次不是要求數量，而是真的要建 BST 出來

首先，將 n = 3 所產生的 BST 重新整理一下

1                1                      2                       3             3
    \                 \                 /      \                  /              / 
      3               2              1       3               2             1
    /                   \                                       /                  \
 2                       3                                   1                    2

可以看出，以 i 為 root 的 BST， i 在 [1,n] 之間

左子樹等同於 1 到 i-1 形成的子樹( 當 1 > i-1 時，為 NULL)

右子樹等同於 i+1 到 n 形成的子樹( 當 i+1 > n 時，為 NULL)

可以用這個性質，搭配 DFS 來建 BST (參考資料)

這邊的 DFS 使用的是 pointer of vector<TreeNode *>，這是要用來節省空間的使用(參考資料)

code 如下
c++

kotlin