首页 > 编程语言 >JAVA学习-练习试用Java实现“不同的二叉搜索树 II”

JAVA学习-练习试用Java实现“不同的二叉搜索树 II”

时间:2024-09-21 10:20:31浏览次数:13  
标签:JAVA int List generateTrees trees II Java TreeNode null

问题:


给定一个整数 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

解答思路:

一、题目分析:本题要求生成所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同二叉搜索树。可以使用递归的方法来解决。

二、主要思路:
1. 定义一个辅助函数 'generateTrees',用于生成所有可能的二叉搜索树。
2. 在 'generateTrees' 函数中,对于每个节点值 i,将其作为根节点,然后递归生成左子树和右子树。
3. 将左子树和右子树的所有可能组合与根节点组合成不同的二叉搜索树。
4. 最后,返回所有生成的二叉搜索树。

三、以下是修改后的代码:

import java.util.ArrayList;
import java.util.List;

public class DifferentBinarySearchTreesII {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }
        return generateTrees(1, n);
    }

    private List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> trees = new ArrayList<>();
        if (start > end) {
            trees.add(null);
            return trees;
        }

        for (int i = start; i <= end; i++) {
            List<TreeNode> leftTrees = generateTrees(start, i - 1);
            List<TreeNode> rightTrees = generateTrees(i + 1, end);

            for (TreeNode left : leftTrees) {
                for (TreeNode right : rightTrees) {
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    trees.add(root);
                }
            }
        }

        return trees;
    }

    public static void main(String[] args) {
        DifferentBinarySearchTreesII solution = new DifferentBinarySearchTreesII();
        int n = 3;
        List<TreeNode> trees = solution.generateTrees(n);
        for (TreeNode tree : trees) {
            System.out.println(tree);
        }
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

(文章为作者在学习java过程中的一些个人体会总结和借鉴,如有不当、错误的地方,请各位大佬批评指正,定当努力改正,如有侵权请联系作者删帖。)

标签:JAVA,int,List,generateTrees,trees,II,Java,TreeNode,null
From: https://blog.csdn.net/weixin_69763181/article/details/142411761

相关文章

  • JAVA学习-练习试用Java实现“子集”
    问题:给定一个整数数组nums,数组中的元素互不相同。返回该数组所有可能的子集(幂集)。解集不能包含重复的子集。你可以按任意顺序返回解集。示例1:输入:nums=[1,2,3]输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]示例2:输入:nums=[0]输出:[[],[0]]提示:1<=num......
  • Java程序员在编写代码时,通常会使用哪些工具和框架?
    Java程序员在日常编码工作中,通常会使用一系列工具和框架来提高开发效率、保证代码质量以及实现快速迭代。以下是一些常用的工具和框架:开发环境和IDEIntelliJIDEA:一个强大的Java集成开发环境,提供了智能代码补全、代码分析、重构工具等功能,是许多Java开发者的首选IDE 。Eclipse......
  • 基于ssm+vue电子元件仓库管理系统(开题报告+程序+论文+java)
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景随着电子产业的迅猛发展,电子元件作为构建各类电子产品的基石,其种类与数量日益庞大,管理难度也随之增加。传统的人工管理模式已难以满足现代企业对高效......
  • 基于java+springboot的大学生校园线上招聘系统(源码+lw+部署文档+讲解等)
    前言......
  • Java生产永不重复的数字
    1.使用AtomicLong生成唯一ID(适用于单机场景)这个示例已经在之前的回答中给出,但我会再次展示它,以便与后续示例保持连贯性。importjava.util.concurrent.atomic.AtomicLong;publicclassUniqueIdGenerator{privatefinalAtomicLongcounter=newAtomicLong(0);......
  • JAVA函数式接口不会用怎么办,一文轻松解决
    函数式接口1.函数式接口的由来​我们知道使用Lambda表达式的前提是需要有函数式接口,而Lambda表达式使用时不关心接口名,抽象方法名。只关心抽象方法的参数列表和返回值类型。因此为了让我们使用Lambda表达式更加的方法,在JDK中提供了大量常用的函数式接口packagecom.bob......
  • java计算机毕业设计体育场馆运营(开题+程序+论文)
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景随着全民健身热潮的兴起和人们对健康生活方式的追求,体育场馆作为促进体育事业发展、满足群众体育需求的重要载体,其运营效率和服务质量日益成为社会各......
  • java计算机毕业设计速运公司物流信息管理系统(开题+程序+论文)
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景随着电子商务的蓬勃发展和全球贸易的日益紧密,速运行业迎来了前所未有的发展机遇与挑战。面对海量订单处理、复杂物流网络构建以及高效客户服务需求的......
  • java计算机毕业设计企业人员考勤管理系统(开题+程序+论文)
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景随着企业规模的不断扩大和市场竞争的日益激烈,人力资源管理成为企业持续发展的关键要素之一。考勤管理作为人力资源管理的重要组成部分,直接关系到企业......
  • java计算机毕业设计数字乡村基础治理系统(开题+程序+论文)
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景随着信息技术的飞速发展,数字化已成为推动社会进步的重要力量。在乡村振兴战略的大背景下,数字乡村基础治理系统的建设显得尤为重要。传统乡村治理方式......