095.不同的二叉搜索树 II

作者：沉默王二
发布时间：2023-10-30T17:18:53.178+0800

---

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

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

难度

中等

示例

示例 1：

输入：n=3

示例 2：

输入：n=1

分析

首先我们来了解一下什么是二叉搜索树。

二叉搜索树是一种二叉树的树形数据结构，其定义如下：

• 空树是二叉搜索树。
• 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。
• 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。
• 二叉搜索树的左右子树均为二叉搜索树。

​ ——引自**二叉搜索树 & 平衡树 - OI Wiki **

简单来说，二叉搜索树需要满足：每个节点的左子树都比自己小、右子树都比自己大。

最简单的情况，一条有序的链表，就算是一个二叉搜索树。例如：

好，接下来我们要知道节点个数为n的二叉搜索树的个数是多少。

假设n个节点的 二叉搜索树 的个数为，为以作为根节点的n个节点的二叉搜索树个数。

我们可以得到这样的式子：

并且当我们分析的时候，还可以得到这样子一个式子：

因为我们知道总数为n的话，当前节点的两个子树，必然是大小为i-1和n-i的两棵二叉搜索树。

综合一下两个公式我们能得到如下式子：

而这，其实就是卡特兰数。

简单来说，卡特兰数就是在某些特定限制条件下，可能的组合或排列的数量。

举一个常见的例子：你有一堆左括号和右括号，要组成一个正确的括号组合（即每个左括号都有一个与之对应的右括号），那么可能的组合数就是一个卡特兰数。

好，我们选择一个数作为根节点，然后分配左右子树，最后按照左右子树的大小继续递归建树即可得到答案。

/**

*publicclassTreeNode{*intval;*TreeNodeleft;*TreeNoderight;*TreeNode(){}*TreeNode(intval){this.val=val;}*TreeNode(intval,TreeNodeleft,TreeNoderight){this.val=val;this.left=left;this.right=right;}}/classSolution{//主方法，接收一个整数n作为参数publicListgenerateTrees(intn){//当n为0时，没有可生成的树，直接返回一个空的列表if(n==0){returnnewLinkedList();}//调用辅助方法generateTrees，生成从1到n的所有可能的二叉搜索树returngenerateTrees(1,n);}
//辅助方法，接收两个整数作为参数，表示生成树的值的范围publicListgenerateTrees(intstart,intend){Listtrees=newLinkedList();//用于存储生成的所有树的列表
//当开始值大于结束值时，表示该区间无有效数字，返回一个包含null的列表if(start>end){trees.add(null);returntrees;}
//遍历从start到end的所有数字，将每一个数字作为根节点for(inti=start;i<=end;i++){//生成所有可能的左子树ListleftTrees=generateTrees(start,i-1);//生成所有可能的右子树ListrightTrees=generateTrees(i+1,end);
//对于每一颗左子树和右子树的组合，创建一个新的树for(TreeNodeleft:leftTrees){for(TreeNoderight:rightTrees){TreeNodenewTree=newTreeNode(i);//创建一个新的树的根节点newTree.left=left;//将当前左子树连接到新树的左侧newTree.right=right;//将当前右子树连接到新树的右侧trees.add(newTree);//将新生成的树添加到trees列表中}}}returntrees;//返回生成的所有树的列表}}

当输入 n = 3 时，我们需要构造所有可能的二叉搜索树，其中树的节点值从 1 到 3。

遍历每个数字 i 从 1 到 3，将其视为根节点，并递归地为其左右子树生成所有可能的结构。

让我们模拟题解的过程：

• i = 1 作为根节点：
• 左子树: 无
• 右子树: 2,3
• 当 2 作为根节点：左子树无，右子树有 3
• 当 3 作为根节点：左子树有 2，右子树无
• 结果：

11

23/32- i = 2 作为根节点：

• 左子树: 1
• 右子树: 3
• 结果：

2

13- i = 3 作为根节点：

• 左子树: 1,2
• 当 1 作为根节点：右子树有 2，左子树无
• 当 2 作为根节点：左子树有 1，右子树无
• 右子树: 无
• 结果：

33

12/21

合并上述所有的结果，我们可以得到5个不同的二叉搜索树。

来看一下题解效率：

这题的核心思想是采用递归的方法来生成所有可能的二叉搜索树。

• 递归基础:
• 当给定的范围内没有数字时（即 start > end），这意味着此处的子树为null，所以我们应该返回一个列表，其中只包含一个null元素。
• 中间节点选择:
• 对于范围内的每个数字 i，我们都尝试将其作为当前树的根节点。也就是说，我们认为每个数字都有可能作为根节点。
• 左、右子树的生成:
• 对于根节点 i，它的左子树应该由 start 到 i - 1 的所有可能树组成，而右子树应该由 i + 1 到 end 的所有可能树组成。
• 使用递归，我们可以得到两个列表：leftTrees 和 rightTrees，分别代表所有可能的左和右子树。
• 然后，我们组合这些左子树和右子树，形成所有可能的树结构。

总结

本题通过总结公式从而得出构建二叉树的方法，这个套路其实也比较普遍，因为它和卡特兰数有关，建议在刷题之余，有意识地去总结对应类别的题目，往往可以给我们带来意想不到的收获。

力扣链接：https://leetcode.cn/problems/unique-binary-search-trees-ii/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3800 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

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

难度

中等

示例

示例 1：

输入：n=3

示例 2：

输入：n=1

分析

首先我们来了解一下什么是二叉搜索树。

二叉搜索树是一种二叉树的树形数据结构，其定义如下：

• 空树是二叉搜索树。
• 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。
• 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。
• 二叉搜索树的左右子树均为二叉搜索树。

​ ——引自**二叉搜索树 & 平衡树 - OI Wiki **

简单来说，二叉搜索树需要满足：每个节点的左子树都比自己小、右子树都比自己大。

最简单的情况，一条有序的链表，就算是一个二叉搜索树。例如：

好，接下来我们要知道节点个数为n的二叉搜索树的个数是多少。

假设n个节点的 二叉搜索树 的个数为，为以作为根节点的n个节点的二叉搜索树个数。

我们可以得到这样的式子：

并且当我们分析的时候，还可以得到这样子一个式子：

因为我们知道总数为n的话，当前节点的两个子树，必然是大小为i-1和n-i的两棵二叉搜索树。

综合一下两个公式我们能得到如下式子：

而这，其实就是卡特兰数。

简单来说，卡特兰数就是在某些特定限制条件下，可能的组合或排列的数量。

举一个常见的例子：你有一堆左括号和右括号，要组成一个正确的括号组合（即每个左括号都有一个与之对应的右括号），那么可能的组合数就是一个卡特兰数。

好，我们选择一个数作为根节点，然后分配左右子树，最后按照左右子树的大小继续递归建树即可得到答案。

/**

*publicclassTreeNode{*intval;*TreeNodeleft;*TreeNoderight;*TreeNode(){}*TreeNode(intval){this.val=val;}*TreeNode(intval,TreeNodeleft,TreeNoderight){this.val=val;this.left=left;this.right=right;}}/classSolution{//主方法，接收一个整数n作为参数publicListgenerateTrees(intn){//当n为0时，没有可生成的树，直接返回一个空的列表if(n==0){returnnewLinkedList();}//调用辅助方法generateTrees，生成从1到n的所有可能的二叉搜索树returngenerateTrees(1,n);}
//辅助方法，接收两个整数作为参数，表示生成树的值的范围publicListgenerateTrees(intstart,intend){Listtrees=newLinkedList();//用于存储生成的所有树的列表
//当开始值大于结束值时，表示该区间无有效数字，返回一个包含null的列表if(start>end){trees.add(null);returntrees;}
//遍历从start到end的所有数字，将每一个数字作为根节点for(inti=start;i<=end;i++){//生成所有可能的左子树ListleftTrees=generateTrees(start,i-1);//生成所有可能的右子树ListrightTrees=generateTrees(i+1,end);
//对于每一颗左子树和右子树的组合，创建一个新的树for(TreeNodeleft:leftTrees){for(TreeNoderight:rightTrees){TreeNodenewTree=newTreeNode(i);//创建一个新的树的根节点newTree.left=left;//将当前左子树连接到新树的左侧newTree.right=right;//将当前右子树连接到新树的右侧trees.add(newTree);//将新生成的树添加到trees列表中}}}returntrees;//返回生成的所有树的列表}}

当输入 n = 3 时，我们需要构造所有可能的二叉搜索树，其中树的节点值从 1 到 3。

遍历每个数字 i 从 1 到 3，将其视为根节点，并递归地为其左右子树生成所有可能的结构。

让我们模拟题解的过程：

• i = 1 作为根节点：
• 左子树: 无
• 右子树: 2,3
• 当 2 作为根节点：左子树无，右子树有 3
• 当 3 作为根节点：左子树有 2，右子树无
• 结果：

11

23/32- i = 2 作为根节点：

• 左子树: 1
• 右子树: 3
• 结果：

2

13- i = 3 作为根节点：

• 左子树: 1,2
• 当 1 作为根节点：右子树有 2，左子树无
• 当 2 作为根节点：左子树有 1，右子树无
• 右子树: 无
• 结果：

33

12/21

合并上述所有的结果，我们可以得到5个不同的二叉搜索树。

来看一下题解效率：

这题的核心思想是采用递归的方法来生成所有可能的二叉搜索树。

• 递归基础:
• 当给定的范围内没有数字时（即 start > end），这意味着此处的子树为null，所以我们应该返回一个列表，其中只包含一个null元素。
• 中间节点选择:
• 对于范围内的每个数字 i，我们都尝试将其作为当前树的根节点。也就是说，我们认为每个数字都有可能作为根节点。
• 左、右子树的生成:
• 对于根节点 i，它的左子树应该由 start 到 i - 1 的所有可能树组成，而右子树应该由 i + 1 到 end 的所有可能树组成。
• 使用递归，我们可以得到两个列表：leftTrees 和 rightTrees，分别代表所有可能的左和右子树。
• 然后，我们组合这些左子树和右子树，形成所有可能的树结构。

总结

本题通过总结公式从而得出构建二叉树的方法，这个套路其实也比较普遍，因为它和卡特兰数有关，建议在刷题之余，有意识地去总结对应类别的题目，往往可以给我们带来意想不到的收获。

力扣链接：https://leetcode.cn/problems/unique-binary-search-trees-ii/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3800 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

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

难度

中等

示例

示例 1：

输入：n=3

示例 2：

输入：n=1

分析

首先我们来了解一下什么是二叉搜索树。

二叉搜索树是一种二叉树的树形数据结构，其定义如下：

• 空树是二叉搜索树。
• 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。
• 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。
• 二叉搜索树的左右子树均为二叉搜索树。

​ ——引自**二叉搜索树 & 平衡树 - OI Wiki **

简单来说，二叉搜索树需要满足：每个节点的左子树都比自己小、右子树都比自己大。

最简单的情况，一条有序的链表，就算是一个二叉搜索树。例如：

好，接下来我们要知道节点个数为n的二叉搜索树的个数是多少。

假设n个节点的 二叉搜索树 的个数为，为以作为根节点的n个节点的二叉搜索树个数。

我们可以得到这样的式子：

并且当我们分析的时候，还可以得到这样子一个式子：

因为我们知道总数为n的话，当前节点的两个子树，必然是大小为i-1和n-i的两棵二叉搜索树。

综合一下两个公式我们能得到如下式子：

而这，其实就是卡特兰数。

简单来说，卡特兰数就是在某些特定限制条件下，可能的组合或排列的数量。

举一个常见的例子：你有一堆左括号和右括号，要组成一个正确的括号组合（即每个左括号都有一个与之对应的右括号），那么可能的组合数就是一个卡特兰数。

好，我们选择一个数作为根节点，然后分配左右子树，最后按照左右子树的大小继续递归建树即可得到答案。

/**

*publicclassTreeNode{*intval;*TreeNodeleft;*TreeNoderight;*TreeNode(){}*TreeNode(intval){this.val=val;}*TreeNode(intval,TreeNodeleft,TreeNoderight){this.val=val;this.left=left;this.right=right;}}/classSolution{//主方法，接收一个整数n作为参数publicListgenerateTrees(intn){//当n为0时，没有可生成的树，直接返回一个空的列表if(n==0){returnnewLinkedList();}//调用辅助方法generateTrees，生成从1到n的所有可能的二叉搜索树returngenerateTrees(1,n);}
//辅助方法，接收两个整数作为参数，表示生成树的值的范围publicListgenerateTrees(intstart,intend){Listtrees=newLinkedList();//用于存储生成的所有树的列表
//当开始值大于结束值时，表示该区间无有效数字，返回一个包含null的列表if(start>end){trees.add(null);returntrees;}
//遍历从start到end的所有数字，将每一个数字作为根节点for(inti=start;i<=end;i++){//生成所有可能的左子树ListleftTrees=generateTrees(start,i-1);//生成所有可能的右子树ListrightTrees=generateTrees(i+1,end);
//对于每一颗左子树和右子树的组合，创建一个新的树for(TreeNodeleft:leftTrees){for(TreeNoderight:rightTrees){TreeNodenewTree=newTreeNode(i);//创建一个新的树的根节点newTree.left=left;//将当前左子树连接到新树的左侧newTree.right=right;//将当前右子树连接到新树的右侧trees.add(newTree);//将新生成的树添加到trees列表中}}}returntrees;//返回生成的所有树的列表}}

当输入 n = 3 时，我们需要构造所有可能的二叉搜索树，其中树的节点值从 1 到 3。

遍历每个数字 i 从 1 到 3，将其视为根节点，并递归地为其左右子树生成所有可能的结构。

让我们模拟题解的过程：

• i = 1 作为根节点：
• 左子树: 无
• 右子树: 2,3
• 当 2 作为根节点：左子树无，右子树有 3
• 当 3 作为根节点：左子树有 2，右子树无
• 结果：

11

23/32- i = 2 作为根节点：

• 左子树: 1
• 右子树: 3
• 结果：

2

13- i = 3 作为根节点：

• 左子树: 1,2
• 当 1 作为根节点：右子树有 2，左子树无
• 当 2 作为根节点：左子树有 1，右子树无
• 右子树: 无
• 结果：

33

12/21

合并上述所有的结果，我们可以得到5个不同的二叉搜索树。

来看一下题解效率：

这题的核心思想是采用递归的方法来生成所有可能的二叉搜索树。

• 递归基础:
• 当给定的范围内没有数字时（即 start > end），这意味着此处的子树为null，所以我们应该返回一个列表，其中只包含一个null元素。
• 中间节点选择:
• 对于范围内的每个数字 i，我们都尝试将其作为当前树的根节点。也就是说，我们认为每个数字都有可能作为根节点。
• 左、右子树的生成:
• 对于根节点 i，它的左子树应该由 start 到 i - 1 的所有可能树组成，而右子树应该由 i + 1 到 end 的所有可能树组成。
• 使用递归，我们可以得到两个列表：leftTrees 和 rightTrees，分别代表所有可能的左和右子树。
• 然后，我们组合这些左子树和右子树，形成所有可能的树结构。

总结

本题通过总结公式从而得出构建二叉树的方法，这个套路其实也比较普遍，因为它和卡特兰数有关，建议在刷题之余，有意识地去总结对应类别的题目，往往可以给我们带来意想不到的收获。

力扣链接：https://leetcode.cn/problems/unique-binary-search-trees-ii/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3800 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412