95. 不同的二叉搜索树 II

心已赠人 2024-04-01 18:55 76阅读 0赞

### 95. 不同的二叉搜索树 II ###

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

##### 示例 1： #####

![在这里插入图片描述][73af330ee6294a2d9c87d4ffb0efa3e9.png]

> 输入：n = 3  
> 输出：\[\[1,null,2,null,3\],\[1,null,3,2\],\[2,1,3\],\[3,1,null,null,2\],\[3,2,null,1\]\]

Input: 3
    Output:
    [
      [1,null,3,2],
      [3,2,null,1],
      [3,1,null,null,2],
      [2,1,3],
      [1,null,2,null,3]
    ]
    Explanation:
    The above output corresponds to the 5 unique BST's shown below:
    
       1         3     3      2      1
        \       /     /      / \      \
         3     2     1      1   3      2
        /     /       \                 \
       2     1         2                 3

##### 示例 2： #####

> 输入：n = 1  
> 输出：\[\[1\]\]

##### 提示： #####

1 < = n < = 8 1 <= n <= 8 1<=n<=8

#### 思路：分治 ####

对于二叉搜索树，任意一个根节点，其左孩子一定比根节点小；右孩子一定比根节点大，进而可以分解成每一个小部分：

*  每个节点都可以做根节点
 *  确定完根节点，所有比根节点小的节点，一定在其左边
 *  所有比根节点大的结点，一定在其右边

##### 然后我们来进行 分治算法三步走： #####

*  分解：按运算符分成左右两部分，分别求解
 *  解决：实现一个递归函数，输入算式，返回算式解
 *  合并：根据运算符合并左右两部分的解，得出最终解

#### 代码：（Java） ####

import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    
    public class diff_bi_tree {
        
    	
    	 public  static class TreeNode {
        
    	     int val;
    	     TreeNode left;
    	     TreeNode right;
    	     TreeNode() {
        }
    	     TreeNode(int val) {
         this.val = val; }
    	     TreeNode(int val, TreeNode left, TreeNode right) {
        
    	         this.val = val;
    	         this.left = left;
    	         this.right = right;
    	    }
    	}
    
    	public static void main(String[] args) {
        
    		// TODO 自动生成的方法存根
    		int n = 3;
    		List<TreeNode> tree = generateTrees(n);
    	
    		for(TreeNode t : tree) {
        
    			
    			Queue<TreeNode > que = new LinkedList<TreeNode>();
    			que.add(t);
    			int num = 0;
    			while(!que.isEmpty()) {
        
    				TreeNode l = que.poll();
    				if(l != null && l.val != 0) {
        
    					System.out.print(" "+l.val+" ");
    					num++;
    					if(num == n)
    						break;
    				}else {
        
    					System.out.print(" null ");
    				}
    				if(l.left != null && l.val != 0) {
        
    					que.add(l.left);
    				}else if(l.val != 0){
        
    					que.add(new TreeNode(0));
    				}
    				if(l.right != null && l.val != 0) {
        
    					que.add(l.right);
    				}else if(l.val != 0) {
        
    					que.add(new TreeNode(0));
    				}
    			}
    			System.out.println();
    		}
    //		System.out.println(tree);
    	}
    
    
    	public static List<TreeNode> generateTrees(int n) {
        
    		if (n < 1) {
        
    			return new LinkedList<TreeNode>();
    		}
    		return generateSubtrees(1, n);
        }
    
    	private static List<TreeNode> generateSubtrees(int s, int e) {
        
    		// TODO 自动生成的方法存根
    		List<TreeNode> res = new LinkedList<TreeNode>();
    		if(s > e) {
        
    			res.add(null);
    			return res;
    		}
    		for(int i=s; i<=e; i++) {
        
    			List<TreeNode> leftSubtrees = generateSubtrees(s, i - 1);
    			List<TreeNode> rightSubtrees = generateSubtrees(i + 1, e);
    			for(TreeNode left : leftSubtrees) {
        
    				for(TreeNode right : rightSubtrees) {
        
    					TreeNode root = new TreeNode(i);
    					root.left = left;
    					root.right = right;
    					res.add(root);
    				}
    			}
    		}
    		return res;
    	}
    	
    }

##### 输出： #####

![在这里插入图片描述][c5762f5fbf33458fb394751793b9a9ad.png]

##### 注：仅供学习参考 #####

来源：[力扣][Link 1]

[73af330ee6294a2d9c87d4ffb0efa3e9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/dc95cd7c09dd453fbee29e60fe71d52a.png
[c5762f5fbf33458fb394751793b9a9ad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/52b0b78ab3d84b60a35fa146c702b8ae.png
[Link 1]: https://leetcode.cn/problems/unique-binary-search-trees-ii/description/