leetcode95--不同的二叉搜索树 II(java)

article/2024/7/17 20:53:36

不同的二叉搜索树 II

  • leetcode95 -- 不同的二叉搜索树 II
    • 题目描述
  • 解题思路
  • 代码演示
  • 二叉树专题

leetcode95 – 不同的二叉搜索树 II

原题链接:
https://leetcode.cn/problems/unique-binary-search-trees-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]]

示例2:
输入:n = 1
输出:[[1]]

提示:
1 <= n <= 8

解题思路

我们用递归去解答.
递归时首先选择不同的数字来当头节点,
选中头节点后,左树能选的数字只能比他小的.
右边子树能选的数字要比这个这个数字大
这样是为了满足搜索二叉树,.
这样递归下去,我们就可以得到左树能组成的所有可能
得到右树所有的可能
然后把两边的可能进行排列组合
组成一颗树,加到集合中,进行返回.

代码演示

/*** Definition for a binary tree node.* public 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;*     }* }*/
class Solution {public List<TreeNode> generateTrees(int n) {if(n == 1){List<TreeNode> ans = new ArrayList<>();ans.add(new TreeNode(n));}return process(1,n);}/*** 递归* L 左边界* R 右边界*/public List<TreeNode> process(int L ,int R){List<TreeNode> ans = new ArrayList<>();//base case if(L > R){ans.add(null);return ans;}//从左边界到右边界依次选择一个数字当头节点for(int i = L ; i <= R;i++){// 左树所有的可能组合//因为是搜索二叉树,左边的节点的值要比头节点小,//选择一个数当头节点后,//左树可选数字只能是小于当前数字的List<TreeNode> lefts = process(L,i - 1);//右树边界 List<TreeNode> rights = process(i + 1,R);for(TreeNode left : lefts){for(TreeNode rig : rights){//排列组合 进行把左树所有的组合和右树所有的组合,//组成不同的树,加到集合中TreeNode head = new TreeNode(i);head.left = left;head.right = rig;ans.add(head);}}}return ans;}
}

二叉树专题

leetcode96–不同的二叉搜索树

二叉搜索树中第K小的元素

从二叉搜索树到更大和树

根据前序和后序遍历构造二叉树

最大二叉树


http://www.ngui.cc/article/show-1200651.html

相关文章

1036 Boys vs Girls(38行代码)

分数 25 全屏浏览题目 切换布局 作者 CHEN, Yue 单位 浙江大学 This time you are asked to tell the difference between the lowest grade of all the male students and the highest grade of all the female students. Input Specification: Each input file contai…

Task 异步编程教程

系列文章目录 Task 异步编程教程 系列文章目录前言常见的用法&#xff1a; Task 异步编程教程目录1. 异步编程基础1.1 异步操作的概念和优势1.2 使用 async 和 await 关键字定义异步方法1.3 异步方法的返回类型和特点 2. Task 类的基础2.1 Task 类的构造方法和静态方法2.2 Task…

Linux :: 【基础指令篇 :: 文件内容操作:(4)】:: head / tail 指令 :: 指定查看文件的部分内容 | 查看前 n 行内容

前言&#xff1a;本篇是 Linux 基本操作篇章的内容&#xff01; 笔者使用的环境是基于腾讯云服务器&#xff1a;CentOS 7.6 64bit。 学习集&#xff1a; C 入门到入土&#xff01;&#xff01;&#xff01;学习合集Linux 从命令到网络再到内核&#xff01;学习合集 注&#xff…

Java学习路线(21)——网络通信

一、网络通信三件套 1、IP地址&#xff1a; 设备在网络中的地址&#xff0c;唯一标识 概念&#xff1a; Internet Protocal&#xff0c;简称为IP&#xff0c;全称“互联网协议地址”。 常见分类&#xff1a; IPv4&#xff08;32位&#xff09; 和 IPv6&#xff08;128位&#…

从零开始的力扣刷题记录-第四十六天

力扣每日四题 507. 完美数-简单661. 图片平滑器-简单1652. 拆炸弹-简单1156. 单字符重复子串的最大长度-中等总结 507. 完美数-简单 题目描述&#xff1a; 对于一个 正整数&#xff0c;如果它和除了它自身以外的所有 正因子 之和相等&#xff0c;我们称它为 「完美数」。 给定…

== 和 equals 的区别是什么?

解读 对于基本类型和引用类型 的作用效果是不同的&#xff0c;如下所示&#xff1a; 基本类型&#xff1a;比较的是值是否相同&#xff1b;引用类型&#xff1a;比较的是引用是否相同&#xff1b; 代码示例&#xff1a; String x "string"; String y "st…

推进印度制造受挫,苹果仍踢出13家中国企业,一条道走到黑?

苹果公布了2022年的供应商名单&#xff0c;让人惊讶的是苹果将13家中国供应商踢出了供应链&#xff0c;而美国、日本的供应商却有所增加&#xff0c;似乎苹果仍然在降低对中国制造的依赖&#xff0c;这对于苹果来说未必是好事。 一、苹果的印度制造计划受挫 数年前苹果推动印度…

这么好看的头像,岂不拿下!

❝ 如此好看的头像&#xff0c;怎么能不喜欢&#xff1f;&#xff1f;&#xff1f; ❞ 代码放在了最后 后续还会出一个工具&#xff0c;以便于随时打开下载。 看上述的头像是不是还是很不错的。看着网站还是✨✨每天都会有更新的✨✨。 所以&#xff0c;我动手了&#xff0c;下…

Linux共享内存 和相关的 shm函数 shmget,shmat,shmdt,shmctl函数

目录 一、什么是共享内存二、使用共享内存的准备和收尾工作三、shmget函数&#xff08;shared memory get&#xff09;四、关联函数shmat五、解除函数shmdt六. shmctl函数&#xff0c;删除共享内存七、相关shell命令八、共享内存的状态 一、什么是共享内存 1、共享内存的定义 …

VMware ESXi 8.0b Unlocker OEM BIOS 集成 REALTEK 网卡驱动和 NVMe 驱动 (集成驱动版)

VMware ESXi 8.0b Unlocker & OEM BIOS 集成 REALTEK 网卡驱动和 NVMe 驱动 (集成驱动版) 发布 ESXi 8.0 集成驱动版&#xff0c;在个人电脑上运行企业级工作负载 请访问原文链接&#xff1a;https://sysin.org/blog/vmware-esxi-8-sysin/&#xff0c;查看最新版。原创作…