东风夜放花千树，更吹落、星如雨。宝马雕车香满路。凤箫声动，玉壶光转，一夜鱼龙舞。
蛾儿雪柳黄金缕，笑语盈盈暗香去。众里寻他千百度，蓦然回首，那人却在，灯火阑珊处。

辛弃疾《青玉案·元夕》

题目描述

leetcode链接:

给你一个整数 nn ，请你生成并返回所有由 nn 个节点组成且节点值从 11 到 nn 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

示例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≤81 \leq n \leq 8

二叉树节点定义以及接口函数签名

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {

    }
};

解题思路

考虑使用动态规划算法，定义一个二维数组dpdp，其元素为vector<TreeNode∗>vector<TreeNode *>，dp[i][j]dp[i][j]保存了节点值从ii到jj的所有互不相同的二叉搜索树。dp[1][n]dp[1][n]就是我们需要的结果。

现在考虑节点值从ii到jj有多少互不相同的二叉搜索树，我们可以通过根节点的不同来区分这些二叉树，即以节点值ii为根节点的二叉树、以i+1i+1为根节点的二叉树…以jj为根节点的二叉树。

当根节点为kk时(i<=k<=j)(i <= k <= j)，其左子树的集合为dp[i][k−1]dp[i][k-1]，其右子树的集合为dp[k+1][j]dp[k+1][j]。我们可以通过排列组合来求得根节点为k的所有二叉树。

具体实现

这里仅给出C++实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        vector<TreeNode *> dp[16][16];

        for(int i=1;i<=n+1;i++) {
            TreeNode * t = new TreeNode(i);
            dp[i][i].push_back(t);
            dp[i][i-1].push_back(nullptr);
        }

        for(int len=1;len<n;len++) {
            for(int i=1;i+len<=n;i++) {
                for(int j=i;j<=i+len;j++) {
                    // j作为头节点
                    for(TreeNode * left : dp[i][j-1]) {
                        for(TreeNode * right : dp[j+1][i+len]) {
                            TreeNode * t = new TreeNode(j, left, right);
                            dp[i][i+len].push_back(t);
                        }
                    }
                }
            }
        }
        return dp[1][n];
    }
};

仅返回不同二叉树的数量

本题的一个简单版本是只返回不同二叉树的数量，原理同上，现给出rust代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
impl Solution {
    pub fn num_trees(n: i32) -> i32 {
        let n = n as usize;
        let mut dp = [[0; 32]; 32];

        for i in 1..(n+2) {
            dp[i][i] = 1;
            dp[i][i-1] = 1;
        }

        for len in 1..n {
            for i in 1..(n-len+1) {
                for j in i..(i+len+1) {
                    dp[i][i+len] += dp[i][j-1] * dp[j+1][i+len];
                }
            }
        }

        dp[1][n] 
    }
}