二叉树经典例题
前言:
本文主要讲解了关于二叉树的简单经典的例题。
因为二叉树的特性,所以关于二叉树的大部分题目,需要利用分治的思想去递归解决问题。
分治思想:
把大问题化简成小问题(根节点、左子树、右子树),返回条件就是最小规模的子问题!
一、二叉树中结点的个数
思路:
采用分而治之的思想, 先访问左子树,再访问右子树,然后再加上自己的个数也就是1。
原码:
//采用分治的思想去解决
int TreeSize(BTNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;/*if (root == NULL)return 0;else{return TreeSize(root->left) + TreeSize(root->right) + 1;}*/
}
二、二叉树中叶子结点的个数
思路:
分为三个判断条件。
- 如果是空结点,就返回0
- 如果是叶子结点就返回1
- 不满足上述两种情况,就继续访问左子树+右子树
原码:
int TreeLeafSize(BTNode* root)
{if (root == NULL)return 0;if (root->left == NULL && root->right == NULL)return 1;return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
三、求第k层的结点个数
思路:
当前树的第k层 = 左子树的k-1层 + 右子树的k-1层,以此类推
当k == 1时,如果不为空结点,就返回1,如果是空结点就返回0。
原码:
int TreeKLevel(BTNode* root, int k)
{assert(k > 0);if (root == NULL)return 0;if (k == 1){return 1;}return TreeKLevel(root->left, k - 1)+ TreeKLevel(root->right, k - 1);
}
四、判断单值二叉树
965. 单值二叉树
思路:
首先明确等号具有传递性,只要根节点和右节点相等,然后根节点与左结点相等,就说明这颗小树就是单值。
并且这是前序遍历,先遍历根节点,如果根节点不是单值二叉树,那么就没有必要去遍历后面的。
这点可以利用&&与操作符实现,与操作符的特性是只要前者是假,后面就不会执行
原码:
bool isUnivalTree(struct TreeNode* root){//采用前序的思想//利用等于号的传递性if(root == NULL)return true;//跟左节点比较 if(root->left){if(root->val != root->left->val)return false;}//跟右结点比较if(root->right){if(root->val != root->right->val)return false;}return isUnivalTree(root->left) && isUnivalTree(root->right);
}
五、销毁二叉树
思路:
采用后序遍历,防止先销毁根节点,导致左右节点找不到了
原码:
void DestroryTree(BTNode* root)
{//递归必须要有判断条件if (root == NULL)return;//需要后序遍历,不然先销毁根节点,左右子树就找不到了DestroryTree(root->left);DestroryTree(root->right);free(root);root = NULL;
六、在二叉树中根据值搜索结点
思路:
可以直接采取前序遍历,
- 最小子问题就是当结点为空时返回空
- 结点的值就是寻找的值就返回该节点
- 不满足上述条件,就继续递归遍历,先左子树再右子树,如果左子树已经找到结点,直接返回
原码:
BTNode* TreeFind(BTNode* root, int x)
{if (root == NULL)return NULL;if (root->val == x)return root;BTNode* ret = TreeFind(root->left, x);if (ret != NULL)return ret;return TreeFind(root->right, x);
}
七、检查两颗树是否相同
100. 相同的树
思路:
采用分治的思想,把问题逐步缩小,最小子问题就是两个结点是否相同
- 我们首先要清楚是不是空树
- 然后如果一个为空,另一个不为空
- 当结点都存在时,再判断结点的值是否相等
原码:
bool isSameTree(struct TreeNode* p, struct TreeNode* q){//分治子问题变成一个结点一个结点的比较//如果两个都为空if(p == NULL && q == NULL)return true;//如果有一个为空if(p == NULL || q == NULL)return false; //如果两个都不为空if(p->val != q->val)return false;return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}
八、对称二叉树
101. 对称二叉树
思路;
本题跟上一题两颗二叉树是否相同非常相似,只需要将比较的结点改变顺序,因为是对称,所以左节点要跟右节点相等。
原码:
bool isSameTree(struct TreeNode* p, struct TreeNode* q){//分治子问题变成一个结点一个结点的比较//如果两个都为空if(p == NULL && q == NULL)return true;//如果有一个为空if(p == NULL || q == NULL)return false; //如果两个都不为空if(p->val != q->val)return false;return isSameTree(p->left,q->right) && isSameTree(p->right,q->left);
}bool isSymmetric(struct TreeNode* root){return isSameTree(root->left,root->right);
}
九、另一棵树的子树
572. 另一棵树的子树
思路:
这道题也是判断相同树的衍生题目,当根节点与subTree的根节点相同时,可以判断两颗树是否相同,并利用||来判断。
原码:
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){//防止递归到空结点,造成非法访问if(root == NULL)return false;//相同前提是根节点要一致if(root->val == subRoot->val){if(isSameTree(root,subRoot))return true;}//只要发现相同,没有必要进行下面的比较,所以是||return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}
十、二叉树的最大深度
104. 二叉树的最大深度
思路:
我们分别求出左子树和右子树的深度,再返回较大的值。
注意:
我们不能将代码写成上面的形式,首先定位上面的代码是非常差的代码,返回值返回的时候会重新进入函数计算,并且是每一个结点!因此我们需要提前将返回值保存起来,将值进行比较去返回。
原码:
int maxDepth(struct TreeNode* root){if(root == NULL)return 0;int leftmax = maxDepth(root->left) + 1;int rightmax = maxDepth(root->right) + 1;return leftmax > rightmax ? leftmax : rightmax;
}
十一、二叉树的前序遍历
144. 二叉树的前序遍历
思路:
本题并不是简单的递归求解,需要根据题目要求,因为我们用C语言进行求解。
- 数组的大小需要我们先自己求这颗树的结点大小,单独开辟一个函数去求解
- 我们不能递归自己的函数,因为每次递归都需要动态开辟一个新的数组,因此还需要重新创建一个函数去解决
- 注意新的函数中数组下标i的值需要传地址,因为递归过程中有很多i,直接传地址
原码:
//先提前算好二叉树结点的个数,便于开辟动态数组的大小
int TreeSize(struct TreeNode* root)
{return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}void preorder(struct TreeNode* root,int* arr,int* i)//传数组下标的地址,避免使用全局变量的麻烦
{if(root == NULL){return;}arr[(*i)] = root->val;(*i)++;preorder(root->left,arr,i);preorder(root->right,arr,i);
}int* preorderTraversal(struct TreeNode* root, int* returnSize){*returnSize = TreeSize(root);int *arr = (int*)malloc(sizeof(int)*(*returnSize));//需要再创建一个函数用来递归,不然每次调用该函数进行递归都会动态开辟int i = 0;preorder(root,arr,&i);return arr;
}
十二、通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
注意:
*pi++ (*pi)++两者含义不同,为了避免优先级的问题,我们直接加上括号!
原码:
BTNode* BinaryTreeCreate(char* str, int* pi)
{if (str[*pi] == '#'){(*pi)++;return NULL;}BTNode* root = (BTNode*)malloc(sizeof(BTNode) * 1);root->val = str[*pi];(*pi)++;root->left = BinaryTreeCreate(str, pi);root->right = BinaryTreeCreate(str, pi);return root;
}
十三、二叉树的层序遍历
涉及到层序遍历,大部分情况下需要借助队列进行求解。
思路:
上一层带下一层,先进先出。
原码:
十四、判断是否是完全二叉树
思路:
利用层序遍历,如果非空结点是连续的,就是完全二叉树。
如果非空结点是不连续的,中间有空结点,就是非完全二叉树。
原码:
相关文章:

二叉树经典例题
前言: 本文主要讲解了关于二叉树的简单经典的例题。 因为二叉树的特性,所以关于二叉树的大部分题目,需要利用分治的思想去递归解决问题。 分治思想: 把大问题化简成小问题(根节点、左子树、右子树)&…...

什么是指针的指针和指向函数的指针?
理解指针的指针和指向函数的指针对于C语言初学者来说可能会有些挑战,但它们都是非常重要的概念,可以帮助你更好地理解和利用C语言的强大功能。在本文中,我将详细解释这两个概念,包括它们的概念、用途和示例。 指针的指针…...

多个excel合并
目的:将同一个文件下的多个 “京东差评.xlsx” 合并为一个:“京东汇总.xlsx" 代码如下: # -*- coding: utf-8 -*- """ Created on Wed Oct 4 12:52:32 2023author: 64884 """import pandas as pd impor…...

Integrity Plus for Mac,保障网站链接无忧之选
在如今数字化的时代,网站链接的完整性对于用户体验和搜索引擎排名至关重要。如果您是一位网站管理员或者经常需要检查网站链接的人,那么Integrity Plus for Mac(Integrity Plus)将成为您最好的伙伴。 Integrity Plus是一款专业的…...

C#,数值计算——Sobol拟随机序列的计算方法与源程序
1 文本格式 using System; using System.Collections.Generic; namespace Legalsoft.Truffer { /// <summary> /// Sobol quasi-random sequence /// </summary> public class Sobol { public Sobol() { } public static void sobseq(int n,…...

以太网协议介绍(ARP、UDP、ICMP、IP)
以太网协议介绍 一、ARP协议 请求: 应答: ARP协议: 0x0001 0x0800 6 4硬件类型:2个字节,arp协议不仅能在以太网上运行还能在其他类型的硬件上运行。以太网用1来表示; 协议类型:两字节。指的是a…...

【C++】STL详解(十)—— 用红黑树封装map和set
📝个人主页:Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:C学习 🎯长路漫漫浩浩,万事皆有期待 上一篇博客:【C】STL…...

Android学习之路(17) Android Adapter详解
Adapter基础讲解 本节引言 从本节开始我们要讲的UI控件都是跟Adapter(适配器)打交道的,了解并学会使用这个Adapter很重要, Adapter是用来帮助填充数据的中间桥梁,简单点说就是:将各种数据以合适的形式显示到view上,提供 给用户看…...

实验室超声波萃取技术的原理和特点是什么?
梵英超声(fanyingsonic)实验室超声波清洗机 超声波萃取中药材的优越性源于超声波的特殊物理性质。通过压电换能器产生的快速机械振动波,超声波可减少目标萃取物与样品基体之间的作用力,从而实现固液萃取分离。 (1)加速介质质点运…...

用Python操作Word文档,看这一篇就对了!
本文主要讲解Python中操作word的思路。 一、Hello,world! 使用win32com需要安装pypiwin32 pip install pypiwin32 推荐使用python的IDLE,交互方便 1、如何新建文档 from win32com.client import Dispatchapp Dispatch(Word.Application…...

力扣 -- 879. 盈利计划(二维费用的背包问题)
解题步骤: 参考代码: 未优化的代码: class Solution { public:int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {//计划数int lengroup.size();//每一维都多开一行空间vector&…...

虚拟机的三种网络连接模式
文章目录 桥接模式NAT模式主机模式 桥接模式 虚拟系统占用主机网段中的一个IP地址,可以正常上网 NAT模式 主机生成一个非本主机的网段的IP的网卡,同时虚拟系统中使用一个该网段的IP地质,网络数据能通过主机的网卡来代理发送出去࿰…...

SQL调优
# 插入数据 页合并 # order by优化 视频教程:34. 进阶-SQL优化-order by优化_哔哩哔哩_bilibili 在创建索引的时候,如果没有设置顺序,是会默认升序的;但phone想要倒序,则需要额外的排序 根据需要,创建联合…...

python写一个开机启动的选项
创建一个Python脚本,以便用户可以选择在开机时启动它,可以使用pyautogui库来创建一个简单的交互式界面,其中用户可以选择是否将程序添加到开机启动项中 import pyautogui import osdef add_to_startup():# 提示用户选择是否要在开机时启动程序…...

1500*A. Boredom(DP)
Problem - 455A - Codeforces Boredom - 洛谷 解析: 首先统计每个数的个数,并且统计出最大值mx。 问题转换为,从1-mx 中选择任意个数字,使其都不相邻,求最大的总和。 开始没有思路,以为直接选取偶数位和奇…...

小程序关键词排名:优化你的应用在搜索中的地位
曾经,我们沉浸在应用商店的浩瀚海洋中,寻找着那个能够满足我们需求的小程序。而今,作为开发者,你的小程序究竟能否在这个无边的数字海洋中引起更多涟漪呢?故事的开始,恰巧就在这个问题的探寻中。让我们携手…...

OpenGLES:3D立方体纹理贴图
效果展示 一.概述 前几篇博文讲解了OpenGLES绘制多种3D图形,并赋予丰富的色彩,但是在这些3D图形绘制过程中,有一点还没有涉及,就是纹理贴图。 今天这篇博文我会用如下六张图片对立方体进行纹理贴图,实现六个面都是贴…...

线程的概述
#include <pthread.h> int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*start_routine) (void *), void *arg); 功能:创建一个子线程 参数: -thread:传出参数,线程创建成功后,子线程的ID被写到…...

竞赛选题 机器视觉目标检测 - opencv 深度学习
文章目录 0 前言2 目标检测概念3 目标分类、定位、检测示例4 传统目标检测5 两类目标检测算法5.1 相关研究5.1.1 选择性搜索5.1.2 OverFeat 5.2 基于区域提名的方法5.2.1 R-CNN5.2.2 SPP-net5.2.3 Fast R-CNN 5.3 端到端的方法YOLOSSD 6 人体检测结果7 最后 0 前言 ǵ…...

python绘图系统27:matplotlib中平面坐标、极坐标和三维坐标的所有绘图函数
文章目录 绘图函数列表为DrawType添加这些绘图函数绘图类别跳转坐标系坐标源代码 绘图函数列表 下面整理了几乎所有matplotlib中的绘图函数,及其在不同坐标轴下的表现。 函数类别2Dpolar3D备注imshow图像X❌❌pcolormesh伪彩图[X,Y,]ZX,Y,Z❌plot曲线图x[,y]x[,y]…...

国庆中秋宅家自省: Python在Excel中绘图尝鲜
【一】国庆中秋: 悟 【国庆中秋】双节来临,相信各位有自己度过的方式,而我却以独特的方式度过了一个说出来不怕各位见笑的双节; 双节到来,没有太多惊喜,也没有太多的负面情绪, 只是喜欢独处,静静反省这些年走过的酸甜苦辣;生活中的许多不欢而散,不期而遇…...

计算机中的进制转换
在计算机软件中,经常需要进行进制转换,这包括二进制、八进制、十进制和十六进制之间的转换。以下是一些常见的转换方法: 二进制转十进制:这是最直接的转换,基本上不需要什么特别的算法。你只需要按照二进制的权值进行…...

Oracle统计信息问题排查常用SQL
Oracle统计信息问题排查常用SQL 对表的基本情况分析统计信息收集作业分析最近一次的统计信息收集修改触发统计信息收集的阈值 对表的基本情况分析 是否为临时表: select owner,table_name,temporary from dba_tables where table_namexxx;是否为分区表:…...

css圣杯布局和双飞翼布局
圣杯布局 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content"widthdevice-width, in…...

机器学习笔记 - 深入研究spaCy库及其使用技巧
一、简述 spaCy 是一个用于 Python 中高级自然语言处理的开源库。它专为生产用途而设计,这意味着它不仅功能强大,而且快速高效。spaCy 在学术界和工业界广泛用于各种 NLP 任务,例如标记化、词性标注、命名实体识别等。 安装,这里使用阿里的源。 pip install spacy…...

网站强制跳转至国家反诈中心该怎么办?怎么处理?如何解封?
在互联网环境中,网站安全是非常重要的。然而,在实际操作过程中,不少网站可能因内容问题、技术安全漏洞等原因被迫下线甚至跳转至国家反诈骗中心网址。面对这一严峻问题,我们如何有效解决,让网站恢复运行并解除强制跳转…...

2023年10月4日
服务器 #include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this);//实例化一个服务器server new QTcpServer(this);//此时,服务器已经成功进入监听状态&…...

MacBook 录制电脑内部声音
MacBook 录制电脑内部声音 老妈喜欢跳广场舞,现在广场舞音频下载都收费了!没办法,只能自己录歌了,外录有杂音大家也都知道,所以就只能采用内录的方式然后再用 Audition 调整一下音量大小。 一、(前置条件&a…...

mysql主从复制和读写分离
在企业应用中,成熟的业务通常数据量都比较大 单台MySQL在安全性、高可用性和高并发方面都无法满足实际的需求 配置多台主从数据库服务器以实现读写分离 所以要做主从服务器,保证安全性 做一写一读服务器,将提升性能 1、什么是读写分离 …...

【计算机网络】网络层-数据平面(学习笔记)
一、网络层提供的服务 1、虚电路服务 通讯前建立虚电路,发送前认为选择路径,所以分组沿着同一条虚电路。 特点:带宽固定 2、数据报服务 数据可能沿着不同路径传输 3、网络层的两个层面 数据层面:源主机到目标主机 控制层面&…...