95. 不同的二叉搜索树 II-蒲公英云

95. 不同的二叉搜索树 II

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

95. 不同的二叉搜索树 II

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

示例 1：

在这里插入图片描述

输入：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;
    }
}