不同的二叉搜索树 II 图解题解

这道题到底在问什么

输入

n=3

输出

5 棵(卡特兰数 C₃)

输入

n=1

输出

1 棵(单节点)

最优解：一步一步想明白

1. 3记住「每个值轮流当根 → 左区间全部形态 × 右区间全部形态」,下面对 n=3 逐棵套它。
2. 4中序 = 升序先看一棵具体的 BST 找感觉:根 2、左 1、右 3。BST 要求左子树都比根小、右子树都比根大,等价于中序遍历严格升序 1、2、3。下面要找的,就是 n=3 时所有满足这一点的不同结构。
3. 5n=3 → 根可取 1/2/3先纵览思路:1、2、3 三个值都可以当根。每选定一个根,左右两个子区间就定下来了,各自再递归。下面从根=1 开始一棵棵拼。
4. 6左空 · 右[2,3]第一步选 1 当根。1 是最小值,左边没有更小的,所以左子树为空;右边要装下 [2,3],得先列出这个区间的所有 BST 形态。
5. 72 当根,3 挂右区间 [2,3] 的第一种形态:让 2 当根。3 比 2 大,只能当 2 的右孩子,得到一条向右的小斜链 2→3。
6. 8接右子树(形态1)把刚才的右子树 2→3 接到根 1 的右边(紫色是新接上的部分)。左边为空、右边这一种形态,组合出一棵完整的树。
7. 91/5第 1 棵成形:1 的右边是 2、2 的右边是 3。验证一下中序遍历正好是 1、2、3 升序,是合法 BST。已生成 1 棵。
8. 103 当根,2 挂左区间 [2,3] 还有第二种形态:让 3 当根。2 比 3 小,当 3 的左孩子,得到 3、左挂 2。
9. 11接右子树(形态2)把第二种右子树(3、左挂 2)接到根 1 右边。这就是以 1 为根的第二棵。
10. 122/5第 2 棵成形。以 1 为根的树到此有 2 棵——正是右区间 [2,3] 的两种形态各配一棵。已生成 2 棵。
11. 13左[1] · 右[3]换 2 当根。左边只剩 [1]、右边只剩 [3],都是单个值,各自只有一种形态(就是它自己)。所以以 2 为根只能拼出 1 棵。
12. 14左1 × 右3把单节点 1 接到 2 的左边、单节点 3 接到右边(紫色)。左右各一种,组合出唯一一棵。
13. 153/5第 3 棵成形:2 当根,左右各挂一个,最平衡。中序仍是 1、2、3。已生成 3 棵。
14. 16左[1,2] · 右空最后让 3 当根。3 是最大值,右边为空;左边要装 [1,2],和刚才的 [2,3] 一样,这个区间也有两种形态。
15. 171 当根,2 挂右区间 [1,2] 的第一种形态:1 当根,2 比 1 大、挂它右边,得到 1→2。
16. 18接左子树(形态1)把左子树(1、右挂 2)接到根 3 的左边。右边为空,组合出一棵。
17. 194/5第 4 棵成形:3 当根、左边是 1、1 的右边是 2。中序还是 1、2、3。已生成 4 棵。
18. 202 当根,1 挂左区间 [1,2] 的第二种形态:2 当根,1 比 2 小、挂左边,得到 2、左挂 1。
19. 21接左子树(形态2)把第二种左子树(2、左挂 1)接到根 3 左边。这是以 3 为根的第二棵。
20. 225/5第 5 棵成形:3、左 2、再左 1,一路向左斜。以 3 为根同样 2 棵。已生成 5 棵,全部集齐。
21. 235 棵 = C₃五棵集齐。按根拆开看:以 1 为根 2 棵、以 2 为根 1 棵、以 3 为根 2 棵,2+1+2=5,正好是卡特兰数 C₃。每棵的「棵数」都等于「左区间形态数 × 右区间形态数」,这就是笛卡尔积的威力。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List, Optional
class TreeNode:
    def __init__(self,val=0,left=None,right=None):
        self.val=val; self.left=left; self.right=right
class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        from functools import lru_cache
        @lru_cache(None)
        def build(l,r):
            if l>r: return (None,)
            ans=[]
            for x in range(l,r+1):
                for a in build(l,x-1):
                    for b in build(x+1,r):
                        ans.append(TreeNode(x,a,b))
            return tuple(ans)
        return list(build(1,n))

#include <algorithm>
#include <functional>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
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*l,TreeNode*r):val(x),left(l),right(r){}};
class Solution{public: vector<TreeNode*> generateTrees(int n){ return build(1,n);} vector<TreeNode*> build(int l,int r){ if(l>r)return {nullptr}; vector<TreeNode*> ans; for(int x=l;x<=r;x++) for(auto a:build(l,x-1)) for(auto b:build(x+1,r)) ans.push_back(new TreeNode(x,a,b)); return ans;} };

import java.util.*;
class TreeNode{int val;TreeNode left,right;TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val,TreeNode left,TreeNode right){this.val=val;this.left=left;this.right=right;}}
class Solution{ public List<TreeNode> generateTrees(int n){ return build(1,n);} List<TreeNode> build(int l,int r){ ArrayList<TreeNode> ans=new ArrayList<>(); if(l>r){ ans.add(null); return ans;} for(int x=l;x<=r;x++) for(TreeNode a:build(l,x-1)) for(TreeNode b:build(x+1,r)) ans.add(new TreeNode(x,a,b)); return ans;} }

复杂度

面试官可能追问