LeetCode 96不同的二叉搜索树&95不同的二叉搜索树Ⅱ

谁借莪１个温暖的怀抱￠ 2023-01-01 10:54 112阅读 0赞

> **微信搜一搜**：`bigsai`  
> **[算法文章题解全部收录在github仓库bigsai-algorithm][github_bigsai-algorithm]**  
> 关注回复**进群**即可加入力扣打卡群，欢迎划水。近期打卡：  
> [LeetCode 92反转链表Ⅱ&93复制ip地址&94二叉树的中序遍历][LeetCode 92_93_ip_94]  
> [LeetCode 90子集Ⅱ&91解码方法][LeetCode 90_91]  
> [LeetCode 88合并两个有序数组&89格雷编码][LeetCode 88_89]

## 96 不同的二叉搜索树Ⅱ ##

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

示例:

输入: 3
    输出: 5
    解释:
    给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
    
       1         3     3      2      1
        \       /     /      / \      \
         3     2     1      1   3      2
        /     /       \                 \
       2     1         2                 3

**分析**  
首先弄清这棵树是一颗二叉搜索树。大的节点只能在右侧，小的在左侧。所以n个节点如果以第i为节点，那么\[1-i-1\]的都在左侧，\[i+1,n\]都在右侧。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70]

如果单单从结构上考虑那么就是：

> 左侧0个数量 **x** 右侧n-1个数量  
> 左侧1个数量 **x** 右侧n-2个数量  
> 左侧2个数量 **x** 右侧n-3个数量  
> ……  
> 左侧n-1个数量 **x** 右侧0个数量

所以这个题父子关系很大，从上就能得到这样的递推，当然这题我们使用动态规划来解决，dp\[i\]表示i个节点所有可以排列的数量。就得到状态转移方程：

> `dp[i]=sum(dp[j]*dp[i-j-1]) j∈[0,i）` （左右子节点之和为i-1）

实现代码为：

class Solution {
        
        public int numTrees(int n) {
        
            if(n<2)return n;
            int dp[]=new int [n+1];
    		 dp[0]=1;
    		 dp[1]=1;
    		 for(int i=2;i<n+1;i++)
    		 {
        
    			 for(int j=0;j<i;j++)
    			 {
        
    				 dp[i]+=dp[j]*dp[i-j-1];
    			 }
    		 }
    		 return dp[n];
        }
    }

## 95不同的二叉搜索树Ⅱ ##

给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。

示例：

输入：3
    输出：
    [
      [1,null,3,2],
      [3,2,null,1],
      [3,1,null,null,2],
      [2,1,3],
      [1,null,2,null,3]
    ]
    解释：
    以上的输出对应以下 5 种不同结构的二叉搜索树：
    
       1         3     3      2      1
        \       /     /      / \      \
         3     2     1      1   3      2
        /     /       \                 \
       2     1         2                 3
     
    
    提示：
    
    0 <= n <= 8

**分析**  
这题和上一题不一样，要求我们返回所有可能的这么一个树，这题的话我还是使用递归的方式，当然不可以无脑递归然后去构造这棵树因为可能会有重复比如 2 3 1 和 2 1 3这个序列构成树的结果是一致的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 1]

所以要考虑一个没有重复但能全部覆盖的策略。这题和上一题有一些不一样的地方就是上一题通过dp可能很多连续数不同但是结构相同我们可以不计算，但这里面每一种情况都需要构建。

所以这题怎么考虑呢？和上题一样，对于n个节点，我们需要考虑的其实就是n个节点每个为根节点的构造可能性。单独考虑第i个节点，第i个节点的left和right分别对应一个节点。所以要找到这种节点组合的排列可能。

在具体实现上我们借助一个递归函数`generateTrees(int start, int end)`表示从start到end的所有满足条件的节点。而在这个递归调用的过程中，我们循环递归分别获取根为第`1,2,3……n`个节点的组成情况(递归调用获取左右部分节点然后新建节点左右部分)。

具体代码为：

public List<TreeNode> generateTrees(int n) {
        
    	   if(n==0)
    		   return new ArrayList<TreeNode>();
    	   return generateTrees(1,n); 
       }
    private List<TreeNode> generateTrees(int start, int end) {
        
    	// TODO Auto-generated method stub
    	List<TreeNode> allList=new ArrayList<TreeNode>();//返回start-end的所有可能的节点
    	if(start>end)//要有null
    	{
        
    		allList.add(null);
    		return allList;
    	}
    
    	for(int i=start;i<=end;i++)
    	{
        
    		List<TreeNode>leftNodes=generateTrees(start,i-1);//左侧
    		List<TreeNode>rightNodes=generateTrees(i+1,end);//右侧
    		for(TreeNode lnode:leftNodes)
    		{
        
    			for(TreeNode rNode:rightNodes)//进行组合
    			{
        
    				TreeNode node=new TreeNode(i);
    				node.left=lnode;
    				node.right=rNode;
    				allList.add(node);//创建新节点添加到集合中
    			}
    		}
    	}
    	
    	return allList;
    }

原创不易，bigsai请你帮两件事帮忙一下:

1.  star支持一下， 您的肯定是我在平台创作的源源动力。
2.  微信搜索「**bigsai**」，关注我的公众号，不仅免费送你电子书，我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。

记得关注、咱们下次再见！

![image-20201114211553660][]

[github_bigsai-algorithm]: https://github.com/javasmall/bigsai-algorithm
[LeetCode 92_93_ip_94]: https://bigsai.blog.csdn.net/article/details/111778579
[LeetCode 90_91]: https://bigsai.blog.csdn.net/article/details/111728376
[LeetCode 88_89]: https://bigsai.blog.csdn.net/article/details/111412194
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70]: /images/20221120/88d5640451c34c54ac4fb09854db8341.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjkzMTcx_size_1_color_FFFFFF_t_70 1]: /images/20221120/dda35a1967cd4ad393b429b56b29c7d7.png
[image-20201114211553660]: /images/20221120/97374705f3834939b653da10b5220055.png