稀碎从零算法笔记Day37-LeetCode:所有可能的真二叉树

news/2024/6/16 10:10:12/文章来源:https://blog.csdn.net/m0_63356844/article/details/137298118

今天的每日一题,感觉理解的还不够深,有待加深理解

题型:树、分治、递归

链接:894. 所有可能的真二叉树 - 力扣(LeetCode)

来源:LeetCode

题目描述

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

题目思路

真二叉树的定义能看明白,但如何枚举出来所有的情况不知道该如何实现

看了题解,发现了一种类似二叉树的先序遍历的枚举方法

讲方法之前先说一下真二叉树的特点:真二叉树的节点的度只能是0或2,那么其节点数只能是奇数。然后真二叉树的子树,自然也是真二叉树,那么子树的节点数也是奇数。同时可以知道,真二叉树没将一个叶子节点变成非叶子,那么他就需要长出两个孩子——即多了1个叶子节点。推广可知:真二叉树的叶子数是【n+1/2】——其中n是节点数。

那么我们就知道了真二叉树的节点数。这样我们就能枚举左右子树分别有 i / n - i - 1 个节点的情况。创一个数组leftSon[i] 来表示左子树节点数为 i 的情况,那么对应的rightSon[i] 表示右子树的情况。

C++代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public://每个节点的出度只能是 0 或者 2 // 真二叉树 节点数一定为奇数// 返回所有真二叉树的情况vector<TreeNode*> allPossibleFBT(int n) {vector<TreeNode *> ans;if(n % 2 == 0)return ans;// 只有一个节点 或者左/右子树只有一个节点,此时递归结束if(n == 1){ans = {new TreeNode(0)};return ans;}// 节点数只能是奇数,左/右子树的节点数也得是奇数个for(int i = 1;i < n ; i += 2){// 对左/右子树的所有节点个数枚举出来vector<TreeNode *>leftSon = allPossibleFBT(i);vector<TreeNode *> rightSon = allPossibleFBT(n-1-i);for(auto L : leftSon){for(auto R : rightSon){ans.emplace_back(new TreeNode(0,L,R));// ans.emplace_back(root);}}}return ans;}
};

结算页面

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1034485.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

第五篇:3.4 用户归因和受众(User attribution and audience) - IAB/MRC及《增强现实广告效果测量指南1.0》

翻译计划 第一篇概述—IAB与MRC及《增强现实广告效果测量指南》之目录、适用范围及术语第二篇广告效果测量定义和其他矩阵之- 3.1 广告印象&#xff08;AD Impression&#xff09;第三篇广告效果测量定义和其他矩阵之- 3.2 可见性 &#xff08;Viewability&#xff09;第四篇广…

解析Flutter应用在iOS环境中的性能优化技巧

本文探讨了使用Flutter开发的iOS应用能否上架&#xff0c;以及上架的具体流程。苹果提供了App Store作为正式上架渠道&#xff0c;同时也有TestFlight供开发者进行内测。合规并通过审核后&#xff0c;Flutter应用可以顺利上架。但上架过程可能存在一些挑战&#xff0c;因此可能…

STM32-03基于HAL库(CubeMX+MDK+Proteus)输入检测案例(按键控制LED)

文章目录 一、功能需求分析二、Proteus绘制电路原理图三、STMCubeMX 配置引脚及模式&#xff0c;生成代码四、MDK打开生成项目&#xff0c;编写HAL库的按键检测代码五、运行仿真程序&#xff0c;调试代码 一、功能需求分析 搭建完成开发STM32开发环境之后&#xff0c;开始GPIO…

【嵌入式硬件】光耦

1.光耦作用 光耦一般用于信号的隔离。当两个电路的电源参考点不相关时,使用光耦可以保证在两边不共地的情况下,完成信号的传输。 2.光耦原理 光耦的原理图如下所示,其内部可以看做一个特殊的“三极管”; 一般的三极管是通过基极B和发射极E间的电流,去控制集电极C和发射极…

01 Python进阶:正则表达式

re.match函数 使用 Python 中的 re 模块时&#xff0c;可以通过 re.match() 函数来尝试从字符串的开头匹配一个模式。以下是一个简单的详解和举例&#xff1a; import re# 定义一个正则表达式模式 pattern r^[a-z] # 匹配开头的小写字母序列# 要匹配的字符串 text "h…

牛客2024年愚人节比赛(A-K)

比赛链接 毕竟是娱乐场&#xff0c;放平心态打吧。。。 只有A一个考了数学期望&#xff0c;其他的基本都是acmer特有的脑筋急转弯&#xff0c;看个乐呵即可。 A 我是欧皇&#xff0c;赚到盆满钵满&#xff01; 思路&#xff1a; 我们有 p 1 p_1 p1​ 的概率直接拿到一件实…

使用Excel连接Azure DevOps自动退出的问题

Azure DevOps Server (原名TFS)是微软公司的软件开发管理平台&#xff0c;也是著名的软件开发过程管理工具&#xff1b;系统中记录了软件开发过程中的需求、问题、缺陷和迭代计划等各种软件开发工作项数据。 对于工作项数据的批量操作(例如新增和编辑)&#xff0c;Excel是一个非…

DevOps与CI/CD简介

DevOps 是一种软件开发和运维的文化、实践和方法论&#xff0c;旨在通过加强开发团队和运维团队之间的合作和沟通&#xff0c;实现快速、高效、可靠的软件交付和运维。DevOps 是由 Development&#xff08;开发&#xff09;和 Operations&#xff08;运维&#xff09;两个单词组…

【随笔】Git -- 高级命令(下篇)(八)

&#x1f48c; 所属专栏&#xff1a;【Git】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &#x1f496; 欢迎大…

QA测试开发工程师面试题满分问答5: 内存溢出和内存泄漏问题

概念阐述 内存溢出&#xff08;Memory Overflow&#xff09;和内存泄漏&#xff08;Memory Leak&#xff09;是与计算机程序中的内存管理相关的问题&#xff0c;它们描述了不同的情况。 内存溢出是指程序在申请内存时&#xff0c;要求的内存超出了系统所能提供的可用内存资源…

文本自动粘贴编辑器:支持自动粘贴并筛选手机号码,让信息处理更轻松

在信息时代的浪潮中&#xff0c;文本处理已成为我们日常工作与生活的重要组成部分。无论是商务沟通、社交互动还是个人事务处理&#xff0c;手机号码的筛选与粘贴都显得尤为关键。然而&#xff0c;传统的文本处理方式效率低下、易出错&#xff0c;已无法满足现代人的高效需求。…

文心一言 vs GPT-4 ----全面横向比较

文心一言 (Wenxin Yiyan) 和 GPT-4 是两个强大的人工智能语言模型&#xff0c;它们在处理自然语言方面表现出了出色的能力。但它们有一些关键的区别和优势。以下是它们的横向比较&#xff1a; 公司和平台&#xff1a; * 文心一言是由百度开发的中文语言模型&#xff0c;专门为…

【C语言】——指针七:数组和指针试题解析

【C语言】——指针七&#xff1a; 前言一、 s i z e o f sizeof sizeof 与 s t r l e n strlen strlen 的对比1.1、 s i z e o f sizeof sizeof1.2、 s t r l e n strlen strlen1.3、 s i z e o f sizeof sizeof 和 s t r l e n strlen strlen 对比 二、数组和指针笔试题解析…

monitor link 联合smart link配合应对复杂的网络

monitor link关键词&#xff1a;上行和下行端口&#xff0c;当上行端口异常&#xff0c;下行端口立即down掉&#xff0c;也就是一种联动机制 如果上行端口里面是smart link方式&#xff0c;则当主从端口都出问题时候&#xff0c;下行端口才会down掉 monitor link 配置步骤 1创…

【LeetCode: 96. 不同的二叉搜索树 + 动态规划】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…

windows下通过vscode访问ubuntu(绝大部分Linux下开发所采用的方案)

前言 本篇博客是介绍VSCode远程连接Ubuntu进行开发的解决方案&#xff0c;前提是安装好了VMWare&#xff0c;Ubuntu&#xff0c;windows下的VSCode。 嵌入式驱动学习专栏将详细记录博主学习驱动的详细过程&#xff0c;未来预计四个月将高强度更新本专栏&#xff0c;喜欢的可以关…

rust项目组织结构和集成测试举例

概述 在学习rust的过程中&#xff0c;当项目结构略微复杂的时候&#xff0c;写集成测试的时候发现总是不能引用项目中的代码&#xff0c;导致编写测试用例失败。查阅了教程&#xff0c;一般举例都很简单。查阅了谷歌和百度以及ai&#xff0c;也没有找到满意的答案。这里记录一…

从《布瓦尔与佩库歇》实践中学习社会科学概论

从《布瓦尔与佩库歇》实践中学习社会科学概论 前情提要《布瓦尔与佩库歇》实践笔记云藏山鹰社会科学概论报告核心--信息形数身知™意合™意气实体过程意气实体过程宇宙学诠释™ 社会科学概论花间流风版导读&#xff0c;马斯克风格演讲[ 一尚韬竹团队供稿&#xff1b;] 内容展开…

如何利用DPU加速Spark大数据处理? | 总结篇

一、总体介绍 1.1 背景介绍 近年来&#xff0c;随着存储硬件的革新与网络技术的突飞猛进&#xff0c;如NVMe SSD和超高速网络接口的普及应用&#xff0c;I/O性能瓶颈已得到显著改善。然而&#xff0c;在2020年及以后的技术背景下&#xff0c;尽管SSD速度通过NVMe接口得到了大幅…

机器学习 | 线性判别分析(Linear Discriminant Analysis)

1 机器学习中的建模 1.1 描述性建模 以方便的形式给出数据的主要特征&#xff0c;实质上是对数据的概括&#xff0c;以便在大量的或有噪声的数据中仍能观察到重要特征。重在认识数据的主要概貌&#xff0c;理解数据的重要特征。 Task&#xff1a;聚类分析&#xff0c;数据降…