LeetCode-894. 所有可能的真二叉树【树 递归 记忆化搜索 动态规划 二叉树】

本文主要是介绍LeetCode-894. 所有可能的真二叉树【树 递归 记忆化搜索 动态规划 二叉树】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

LeetCode-894. 所有可能的真二叉树【树 递归 记忆化搜索 动态规划 二叉树】

  • 题目描述:
  • 解题思路一:分治,递归
  • 解题思路二:动态规划。关键思路是如果构造节点数目为 n 的真二叉树,此时可以从节点数目序列为 [(1,n−2),(3,n−5),⋯ ,(n−2,1)]的真二叉树中构成,按照所有可能的组合数进行枚举,即可构造成节点数目为 n 的真二叉树。即左子树分配1,3,5, ... , n-2个节点。
  • 解题思路三:0

题目描述:

给你一个整数 n ,请你找出所有可能含 n 个节点的 真二叉树 ,并以列表形式返回。答案中每棵树的每个节点都必须符合 Node.val == 0 。

答案的每个元素都是一棵真二叉树的根节点。你可以按 任意顺序 返回最终的真二叉树列表。

真二叉树 是一类二叉树,树中每个节点恰好有 0 或 2 个子节点。

示例 1:
在这里插入图片描述
输入:n = 7
输出:[[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]
示例 2:

输入:n = 3
输出:[[0,0,0]]

提示:

1 <= n <= 20

解题思路一:分治,递归

如果你要为某节点分配一个左节点,那么一定也要为它分配一个右节点。因此,如果 N 为偶数,那一定无法构成一棵满二叉树。

为了列出所有满二叉树的排列,我们可以为左子树分配 x 节点,为右子树分配 N - 1 - x(其中减 1 减去的是根节点)节点,然后递归地构造左右子树。

x 的数目从 1 开始,每次循环递增数目 2(多增加 2 个节点,等于多增加 1 层)。

递归过程
递归最关心的两个问题是:

  • 结束条件
  • 自身调用

对于这个问题来说,结束条件为:

  • 当 N 为偶数时:无法构造满二叉树,返回空数组
  • 当 N == 1 时:树只有一个节点,直接返回包含这个节点的数组
  • 当完成 N 个节点满二叉树构造时:返回结果数组
    当需要构造左右子树时,就进行自身调用。具体的看代码吧~
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:res = []if n == 1:return [TreeNode(0)]if n % 2 == 0: # 结点个数必须是奇数return []left_num = 1 # 左子树分配一个节点right_num = n - 2 # 此时n必大于等于3, 右子树可以分配到 n - 1 - 1 = n - 2 个节点while right_num > 0:left_tree = self.allPossibleFBT(left_num) # 递归构造左子树right_tree = self.allPossibleFBT(right_num) # 递归构造右子树# 具体构造过程for i in range(len(left_tree)):for j in range(len(right_tree)):root = TreeNode(0)root.left = left_tree[i]root.right = right_tree[j]res.append(root) # 注意返回的是树的根节点left_num += 2right_num -= 2return res

时间复杂度:O(2n / n \sqrt n n )
空间复杂度:O(n) 递归调用栈

解题思路二:动态规划。关键思路是如果构造节点数目为 n 的真二叉树,此时可以从节点数目序列为 [(1,n−2),(3,n−5),⋯ ,(n−2,1)]的真二叉树中构成,按照所有可能的组合数进行枚举,即可构造成节点数目为 n 的真二叉树。即左子树分配1,3,5, … , n-2个节点。

动规五部曲:定推初遍举

  1. dp定义:所有可能含 n 个节点的 真二叉树
  2. 推导:dp[n] = 节点数目序列为 [(1,n−2),(3,n−5),⋯ ,(n−2,1)]的真二叉树中构成
  3. 初始化:dp[1] = [TreeNode(0)]
  4. 遍历:按照推导公式来for i in range(3, n + 1, 2): for j in range(1, i, 2):
  5. 举例:注意dp[i]是一个列表
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def allPossibleFBT(self, n: int) -> List[Optional[TreeNode]]:if n % 2 == 0: # 结点个数必须是奇数return []dp = [[] for _ in range(n+1)]dp[1] = [TreeNode(0)]for i in range(3, n + 1, 2):for j in range(1, i, 2):for left_tree in dp[j]:for right_tree in dp[i - 1 - j]:root = TreeNode(0, left_tree, right_tree)dp[i].append(root)return dp[n]

时间复杂度:O(2n / n \sqrt n n )
空间复杂度:O(1)返回值不计入空间复杂度。

解题思路三:0


时间复杂度:O(n)
空间复杂度:O(n)

这篇关于LeetCode-894. 所有可能的真二叉树【树 递归 记忆化搜索 动态规划 二叉树】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/870464

相关文章

MyBatis编写嵌套子查询的动态SQL实践详解

《MyBatis编写嵌套子查询的动态SQL实践详解》在Java生态中,MyBatis作为一款优秀的ORM框架,广泛应用于数据库操作,本文将深入探讨如何在MyBatis中编写嵌套子查询的动态SQL,并结... 目录一、Myhttp://www.chinasem.cnBATis动态SQL的核心优势1. 灵活性与可

Mybatis嵌套子查询动态SQL编写实践

《Mybatis嵌套子查询动态SQL编写实践》:本文主要介绍Mybatis嵌套子查询动态SQL编写方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言一、实体类1、主类2、子类二、Mapper三、XML四、详解总结前言MyBATis的xml文件编写动态SQL

SpringBoot实现Kafka动态反序列化的完整代码

《SpringBoot实现Kafka动态反序列化的完整代码》在分布式系统中,Kafka作为高吞吐量的消息队列,常常需要处理来自不同主题(Topic)的异构数据,不同的业务场景可能要求对同一消费者组内的... 目录引言一、问题背景1.1 动态反序列化的需求1.2 常见问题二、动态反序列化的核心方案2.1 ht

golang实现动态路由的项目实践

《golang实现动态路由的项目实践》本文主要介绍了golang实现动态路由项目实践,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习... 目录一、动态路由1.结构体(数据库的定义)2.预加载preload3.添加关联的方法一、动态路由1

IDEA下"File is read-only"可能原因分析及"找不到或无法加载主类"的问题

《IDEA下Fileisread-only可能原因分析及找不到或无法加载主类的问题》:本文主要介绍IDEA下Fileisread-only可能原因分析及找不到或无法加载主类的问题,具有很好的参... 目录1.File is read-only”可能原因2.“找不到或无法加载主类”问题的解决总结1.File

Python Selenium动态渲染页面和抓取的使用指南

《PythonSelenium动态渲染页面和抓取的使用指南》在Web数据采集领域,动态渲染页面已成为现代网站的主流形式,本文将从技术原理,环境配置,核心功能系统讲解Selenium在Python动态... 目录一、Selenium技术架构解析二、环境搭建与基础配置1. 组件安装2. 驱动配置3. 基础操作模

mysql递归查询语法WITH RECURSIVE的使用

《mysql递归查询语法WITHRECURSIVE的使用》本文主要介绍了mysql递归查询语法WITHRECURSIVE的使用,WITHRECURSIVE用于执行递归查询,特别适合处理层级结构或递归... 目录基本语法结构:关键部分解析:递归查询的工作流程:示例:员工与经理的层级关系解释:示例:树形结构的数

慢sql提前分析预警和动态sql替换-Mybatis-SQL

《慢sql提前分析预警和动态sql替换-Mybatis-SQL》为防止慢SQL问题而开发的MyBatis组件,该组件能够在开发、测试阶段自动分析SQL语句,并在出现慢SQL问题时通过Ducc配置实现动... 目录背景解决思路开源方案调研设计方案详细设计使用方法1、引入依赖jar包2、配置组件XML3、核心配

springboot使用Scheduling实现动态增删启停定时任务教程

《springboot使用Scheduling实现动态增删启停定时任务教程》:本文主要介绍springboot使用Scheduling实现动态增删启停定时任务教程,具有很好的参考价值,希望对大家有... 目录1、配置定时任务需要的线程池2、创建ScheduledFuture的包装类3、注册定时任务,增加、删

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾