二叉树路径相关算法题|带权路径长度WPL|最长路径长度|直径长度|到叶节点路径|深度|到某节点的路径非递归(C)

带权路径长度WPL

二叉树的带权路径长度(WPL)是二叉树所有叶节点的带权路径长度之和,给定一棵二叉树T,采用二叉链表存储,节点结构为
在这里插入图片描述

其中叶节点的weight域保存该节点的非负权值,设root为指向T的根节点的指针,设计求WPL的算法

算法思想

![[Pasted image 20241120144005.png]]

方法1,树中全部叶节点的带权路径长度之和
采用递归思想
二叉树的WPL值 = 树中全部叶节点的带权路径长度之和 = 根节点左子树中全部叶节点的带权路径长度之和 + 根节点右子树中全部叶节点的带权路径长度之和
叶节点的带权路径长度 = 该节点的weight域的值 x 该节点的深度
设根节点的深度为0,若某节点的深度为d,其子节点的深度为d+1
递归过程中,如果遍历到叶节点,返回该节点的带权路径长度,否则返回其左右子树的带权路径长度之和

先遍历5,d是0,不是叶子节点,递归3和7,d为1,3不是叶子节点,7是叶子节点,返回1x7,再递归1和4,d为2,都是叶子节点,返回1x2和4x2,所以WPL为2+8+7=17

typedef struct node
{int weight;struct node *left, *right;
}BTNode;// 传入根节点,调用递归函数,初始深度d为0
int WPL(BTNode* root)
{return WPL1(root, 0);
}// 传入节点和该节点的深度
int WPL1(BTNode* root, int d)
{// 如果该节点是叶子节点,返回该叶子节点的weightxd,也就是带权路径长度if (root->left == NULL && root->right == NULL)return (root->weight * d);// 否则递归该节点的左孩子和右孩子,子节点的深度为根节点的深度+1elsereturn (WPL1(root->left, d + 1) + WPL1(root->right, d + 1));
}

WPL1是一个递归函数,用来计算从当前节点开始的WPL

最长路径长度

给定一个二叉树的root,返回最长的路径的长度,这个路径中的每个节点具有相同值。这条路径可以经过也可以不经过根节点。两个节点之间的路径的长度由它们之间的边数表示

算法思想

符合要求的左子树路径最大长度leftpath,符合要求的右子树路径最大长度rightpath,最后的路径长度为当前路径,与rightpath+leftpath最大值,注意全局变量的初始化位置
![[Pasted image 20241120204702.png]]

第一层
递归计算root的左右孩子的最长单向路径
右节点存在且与当前节点值相等,都是5
rightpath = right+1
![[Pasted image 20241120205655.png]]

第二层
right是右节点的DFS返回的值;
递归计算这个节点的左右孩子的最长单向路径,
同样右节点存在且与当前值相等,都是5
rightpath = right+1
![[Pasted image 20241120205727.png]]

第三层
right是右孩子返回的值,
递归左右孩子,为空,返回0
left和right都是0,path也是0,最后返回0
返回第二层
right是0,rightpath是1,path更新为1,返回1
返回第一层
right是1,rightpath是2,path更新为2,返回2

int path;   // 全局变量,用于存储当前发现的最长路径长度
// 返回两个正数中的较大值
int Max(int a, int b)
{return a >= b ? a : b;
}
// 递归地计算以root为根的子树中,以相同节点值构成的最长路径
int DFS(BTNode* root)
{// 如果当前节点为空,返回0,因为没有路径if (root == NULL)return 0;int left;int right;int leftpath = 0;int rightpath = 0;// 递归计算左子树和右子树的最长单向路径// left是左子树的最长路径,right是右子树的最长路径left = DFS(root->left);right = DFS(root->right);// 如果左节点存在且与当前节点值相等,最长路径+1if ((root->left) && (root->left->val == root->val))leftpath = left + 1;// 如果右节点存在且与当前节点值相等,最长路径+1if ((root->right) && (root->right->val == root->val))rightpath = right + 1;// leftpath+rightpath,当前节点处的最长路径的长度,经过当前节点// 更新pathpath = Max(path, leftpath + rightpath);// 返回从当前节点向下延伸的最长单项路径,用于供上层节点继续计算return Max(leftpath, rightpath);
}
int longestUnivaluePath(BTNode* root)
{if (root == NULL)return 0;path = 0;DFS(root);return path;
}

直径长度

给定一个二叉树,计算它的直径长度。一棵二叉树的直径长度是任意两个节点路径长度中的最大值。这条路径可能穿过也可能不穿过根节点

算法思想

递归求得节点的左子树的最大深度和右子树的最大深度,相加便是经过该节点的直径,遍历每个节点,更新最大值便可得到该二叉树的最大直径。

  1. 写出一个求树的最大深度的函数
  2. 递归调用这个函数,求得每个节点的左子树最大深度和右子树最大深度,相加

![[Pasted image 20241120211158.png]]

第一层
将rootA传入depth求深度,传入sum记录直径
递归计算左右子树B和C的深度
第二层
B继续递归左右子树的深度,D和F
C为叶子节点,没有左右孩子,left和right为0,new也就是直径为1,sum更新为1,返回深度为1
第三层
D为叶子节点,new为1,sum还是1,返回深度为1
F为叶子节点,new为1,sum还是1,返回深度为1
返回第二层
B,的left和right都是1,B的new也就是直径是3,sum更新为3,返回深度为2
返回第一层
A,left为2,right为1,new也就是直径为4,sum更新为4,返回深度为3
最后sum=4,返回sum-1 = 3

// 返回两个整数中的较大值
int max(int a, int b)
{return a > b ? a : b;
}// 递归计算二叉树的深度,同时更新全局变量记录直径
int depth(BTNode* root, int* sum)
{// 如果当前节点为空,返回深度为0if (root == NULL)return 0;// 左子树的最大深度int left = depth(root->left, sum);// 右子树的最大深度int right = depth(root->right, sum);// 经过根节点的直径,左子树最大深度与右子树最大深度之和int new = left + right + 1;// 更新sum,记录到目前为止的最大直径*sum = max(*sum, new);// 返回该节点深度的最大值,等于左右子树的最大深度+1return max(left, right) + 1;
}int dimeterBT(BTNode* root)
{if (root == NULL)return 0;int sum = 0;depth(root, &sum);// 返回sum-1,将节点数转换为边数作为直径的定义return sum - 1;
}

到叶节点路径

给你一个二叉树的根节点root,按任意顺序,返回所有从根节点到叶子节点的路径

算法思想

深度优先遍历二叉树,要考虑当前节点以及它的孩子节点,如果当前节点不是叶子节点,则在当前的路径末尾添加该节点,并继续递归遍历该节点的每一个孩子节点
如果当前节点是叶子节点,则在当前路径末尾添加该节点后就得到了从根节点到叶子节点的路径
![[Pasted image 20241121142757.png]]

将根节点的值1,入到stack深度下标的位置上,深度为0
![[Pasted image 20241121142855.png]]

有左右孩子,先递归左孩子,深度+1=1
2,入栈
![[Pasted image 20241121143227.png]]

有右孩子,递归右孩子,5入栈,depth为2
![[Pasted image 20241121143316.png]]

这时候左右孩子节点都为空
将1->2->5的路径保存

  • 动态分配一个字符串缓冲区tmp。用于存储当前路径的字符串
    1001是缓冲区的长度
  • len=0,记录路径字符串的当前长度,即字符串的写入位置,起始为0,表示字符串从头开始写入
  • 遍历当前路径中的所有节点值,即stack;使用sprintf追加到路径字符串tmp中
  • 添加叶节点值,在路径字符串的末尾,添加当前叶子节点的值
  • 将路径字符串存储到结果数组

返回1节点,递归右孩子3,深度为1,入栈,会覆盖掉2,变成3

// 定义二叉树节点结构 
typedef struct node 
{ int val; struct node* left; struct node* right; 
} BTNode; // 辅助函数:递归生成路径 
void generatePaths(BTNode* root, char** paths, int* returnSize, int* stack, int depth) 
{ if (root == NULL) return; // 将当前节点加入路径栈 stack[depth] = root->val; // 如果是叶子节点,生成路径字符串 if (root->left == NULL && root->right == NULL) { // 分配路径字符串 char* tmp = (char*)malloc(1001); int len = 0; // 构建路径字符串 for (int i = 0; i < depth; i++) { len += sprintf(tmp + len, "%d->", stack[i]); } // 添加叶子节点值 sprintf(tmp + len, "%d", root->val); // 将路径存储到结果数组 paths[(*returnSize)++] = tmp; return; } // 递归遍历左、右子树 generatePaths(root->left, paths, returnSize, stack, depth + 1); generatePaths(root->right, paths, returnSize, stack, depth + 1); 
} // 主函数:生成所有路径 
char** binaryTreePaths(BTNode* root, int* returnSize) 
{ // 分配结果数组 char** paths = (char**)malloc(sizeof(char*) * 1001); *returnSize = 0; // 路径栈 int stack[1001]; // 调用递归函数 generatePaths(root, paths, returnSize, stack, 0); return paths; 
}
  • binaryTreePaths,输入:root,二叉树的根节点,returnSize,用来返回路径数量
  • 返回paths,存储路径字符串的数组
  • paths是一个指针数组,用来存储每条路径的字符串
  • stack用来记录当前节点的路径值
  • generatePaths用来来递归生成路径

generatePaths

  • 如果节点root为NULL,直接返回,(递归退出条件)
  • 将当前节点的值存入栈stack[depth]
  • depth表示当前路径的深度
    处理叶子节点
  • 创建字符串,遍历路径栈stack,通过sprintf拼接路径值,将路径字符串的结果保存在paths中
  • 增加路径数量returnSize
    遍历左右子树
  • 如果当前节点不是叶子节点,遍历递归左子树和右子树
  • 子树深度为depth+1

深度

输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点形成树的一条路径,最长路径的长度为树的深度
9

算法思想

如果二叉树为空,深度为0,如果二叉树只有根节点,深度为1
如果二叉树的根节点只有左子树,深度为左子树的深度+1
如果二叉树的根节点只有右子树,深度为右子树的深度+1
如果二叉树的根节点既有既有左子树又有右子树,深度为左右子树深度最大者+1

int maxDepth(BTNode* root)
{if (root == NULL)return 0;// 当前节点的左子树的深度int Lenleft = maxDepth(root->left);// 当前节点的右子树的深度int Lenright = maxDepth(root->right);// 返回左右子树的深度的较大者+1return Lenleft > Lenright ? Lenleft+1 : Lenright+1;
}

到某节点的路径非递归

假设二叉树采用链式存储结构进行存储,root为根节点,p为任意给定节点
求从根节点到p之间路径的非递归算法

算法思想

采用后序非递归遍历二叉树,栈中保留从根节点到当前节点的路径上的所有节点
![[Pasted image 20241121145246.png]]

  • cur是当前遍历的节点
  • s是栈,用来存储当前节点及其祖先节点,用于后续回溯
  • tag数组用于标记每个节点的左右子树是否已经被访问
  • top用来表示栈的当前高度
    while循环用于实现二叉树的深度优先遍历,只要当前节点不为空或者栈不为空就继续
    while循环表示从当前cur节点开始,一直往左遍历,直到没有左子树为止
    每次访问一个节点,将该节点入栈,并设置tag为0,表示其右子树未被访问
    如果当前节点cur就是p,就打印从根节点到p的路径,通过s栈表示

由于p是3节点,将1,2,4,入栈
![[Pasted image 20241121150425.png]]

处理右子树,检查tap里的数据,如果右子树被访问过,就弹出该节点,跳过所有已经完全访问过的节点
如果该节点的右子树未被访问,就会进入右子树进行遍历,

遍历4节点的右子树,tag置为1,节点为空,直接返回
![[Pasted image 20241121150742.png]]

这是循环过来,4被访问过,出栈
![[Pasted image 20241121150805.png]]

再遍历2的右节点,
![[Pasted image 20241121150827.png]]

// 查找从根节点到指定节点p的路径
void Path(BTNode* root, BTNode* p)
{if (root == NULL || p == NULL)return;BTNode* cur = root;// 存储节点路径的栈int s[MaxSize];// 栈的当前高度int top = 0;// 标记左右子树是否访问过int tag[MaxSize] = {0};while (cur || top > 0){// 向左走直到最左叶子节点while (cur){// 将当前节点入栈s[++top] = cur;// 标记为未访问右子树tag[top] = 0;// 找到目标节点pif (cur == p){printf("从根节点到p节点的路径为\n");for (int i = 1; i <= top; i++){printf("%d", s[i]->data);if (i < top)printf("->");printf("\n");return;}}// 继续遍历左子树cur = cur->left;}// 如果当前节点的左子树遍历完,回溯到父节点while (top > 0 && tag[top] == 1)// 出栈top--;// 访问右子树if (top > 0){// 访问当前节点的右子树cur = s[top];// 进入右子树cur = cur->right;// 标记右子树已访问tag[top] = 1;}}
}

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

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

相关文章

飞桨大模型PaddleOCR

一、新建项目PaddleOCRProject 二、查看开源 pip install paddlepaddle pip install paddleocr指定镜像源下载才快&#xff1a; pip install paddlepaddle -i https://pypi.tuna.tsinghua.edu.cn/simple pip install paddleocr -i https://pypi.tuna.tsinghua.edu.cn/simple 三…

Python创建虚拟环境报错:Error: Command......

文章目录 环境说明问题描述原因分析解决方法 环境说明 系统 # lsb_release -a No LSB modules are available. Distributor ID: Ubuntu Description: Ubuntu 22.04.4 LTS Release: 22.04 Codename: jammyPython版本 # python3 --version Python 3.13.0问题描…

Linux INPUT 子系统详解

目录 一、引言 二、INPUT 子系统的架构 1.输入设备驱动层 2.核心层 3.事件处理层 三、INPUT 子系统的工作原理 1.设备注册与初始化 2.事件产生与提交 3.事件分发与处理 4.应用程序访问输入设备 四、使用 INPUT 子系统进行设备驱动开发 1.编写输入设备驱动程序 2.注…

sql注入报错分享(mssql+mysql)

mysql mysql的报错内容比较多 网上也有比较多的 这里重复的就不多介绍了。一笔带过 溢出类 bigint 当超过mysql的整形的时候&#xff0c;就会导致溢出&#xff0c;mysql可能会将错误信息带出。这里user()是字母默认为0 取反以后1可能就会导致异常。 报错特征 BIGINT UNSIG…

JVM(五、垃圾回收器)

经典的垃圾回收器大概有7种&#xff0c;这些收集器的目标、特性、原理、使用场景都有所区别&#xff0c;有的适用于年轻代&#xff0c;有的适用于老年代&#xff0c;图中展示的就是这7中垃圾回收器&#xff0c;如果两个垃圾回收器有连线&#xff0c;则表明可以配合使用。这个关…

雅思阅读TFNG题型7大解题思路

雅思阅读TFNG题型7大解题思路&#xff0c;全在这了‼️ ⚠️在徘徊在6-6.5的同学有很大的共性就是对题型不够熟悉&#xff0c;我记得我当时卡6.5的时候我有时候分不清NG和F&#xff0c;有时候又分不清NG 和True&#xff0c;也不知道他有哪几种考我的方法&#xff0c;脑子里没有…

Nuxt3:拉取项目模板失败问题解决方法

问题描述 使用官网提供的命令npx nuxilatest init <project-name> 创建Nuxt3项目时&#xff0c;遇到了拉取项目模板失败的问题&#xff0c;报错信息如下 先分析一下这行命令在做的事情&#xff0c;结合之前的经验来看&#xff0c;似乎是在尝试通过该网址返回的元数据信息…

索引(MySQL)

1. 没有索引&#xff0c;可能会有什么问题 索引&#xff1a;提高数据库的性能&#xff0c;索引是物美价廉的东西了。不用加内存&#xff0c;不用改程序&#xff0c;不用调sql&#xff0c;只要执行 正确的 create index &#xff0c;查询速度就可能提高成百上千倍。但是天下没有…

MybatisPlus之1:快速入门

欢迎来到“雪碧聊技术”CSDN博客&#xff01; 在这里&#xff0c;您将踏入一个专注于Java开发技术的知识殿堂。无论您是Java编程的初学者&#xff0c;还是具有一定经验的开发者&#xff0c;相信我的博客都能为您提供宝贵的学习资源和实用技巧。作为您的技术向导&#xff0c;我将…

菜鸟驿站二维码/一维码 取件识别功能

特别注意需要引入 库文 ZXing 可跳转&#xff1a; 记录【WinForm】C#学习使用ZXing.Net生成条码过程_c# zxing-CSDN博客 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using static System.Net.…

「甲子光年」对话黄翔:从电子签回望中国SaaS“黄金十年”

法大大成立十周年之际&#xff0c;联合「甲子光年」重榜发布《中国电子签十年风云录》&#xff0c;通过应用者、从业者、观察者的不同视角&#xff0c;记录电子签乃至时代发展的风云十年。本期是刊物精彩内容呈现的第一期&#xff0c;扫描下图可获取电子版。 创立法大大之前&am…

【Three.js基础学习】28.Coffee Smoke

前言 /* 补充&#xff1a;材质本身纹理有光源等信息因此能看到模型 gltf.scene.traverse((child) > { if (child.isMesh) { child.material.map null; // 移除贴图 } }); 此时是纯白色&#xff0c;按照正常逻辑 没有光会是灰/黑色 为什么显示白色 1.默认材质颜色 2.材质的表…

Linux(命令行扩展+命令行历史 大白话+图片)

后面也会持续更新&#xff0c;学到新东西会在其中补充。 建议按顺序食用&#xff0c;欢迎批评或者交流&#xff01; 缺什么东西欢迎评论&#xff01;我都会及时修改的&#xff01; 在这里真的很感谢这位老师的教学视频让迷茫的我找到了很好的学习视频 王晓春老师的个人空间…

渗透测试---shell(5)字符串运算符与逻辑运算符

声明&#xff1a;学习素材来自b站up【泷羽Sec】&#xff0c;侵删&#xff0c;若阅读过程中有相关方面的不足&#xff0c;还请指正&#xff0c;本文只做相关技术分享,切莫从事违法等相关行为&#xff0c;本人与泷羽sec团队一律不承担一切后果 目录 一、字符串运算符 创建u.sh文…

06、Spring AOP

在我们接下来聊Spring AOP之前我们先了解一下设计模式中的代理模式。 一、代理模式 代理模式是23种设计模式中的一种,它属于结构型设计模式。 对于代理模式的理解: 程序中对象A与对象B无法直接交互,如:有人要找某个公司的老总得先打前台登记传达程序中某个功能需要在原基…

游戏陪玩系统开发功能需求分析

电竞游戏陪玩系统是一种专门为游戏玩家提供陪伴、指导和互动服务的平台。这类系统通常通过专业的陪玩师&#xff08;也称为陪练师&#xff09;为玩家提供一对一或多对一的游戏陪伴服务&#xff0c;帮助玩家提升游戏技能、享受游戏乐趣&#xff0c;甚至解决游戏中的各种问题。电…

【数据库入门】关系型数据库入门及SQL语句的编写

1.数据库的类型&#xff1a; 数据库分为网状数据库&#xff0c;层次数据库&#xff0c;关系型数据库和非关系型数据库四种。 目前市场上比较主流的是&#xff1a;关系型数据库和非关系型数据库。 关系型数据库使用结构化查询语句&#xff08;SQL&#xff09;对关系型数据库进行…

【2024亚太杯亚太赛APMCM C题】数学建模竞赛|宠物行业及相关产业的发展分析与策略|建模过程+完整代码论文全解全析

第一个问题是&#xff1a;请基于附件 1 中的数据以及你的团队收集的额外数据&#xff0c;分析过去五年中国宠物行业按宠物类型的发展情况。并分析中国宠物行业发展的因素&#xff0c;预测未来三年中国宠物行业的发展。 第一个问题&#xff1a;分析中国宠物行业按宠物类型的发展…

合法三元数量计算

问题描述 小C、小U 和小R 三个好朋友喜欢做一些数字谜题。这次他们遇到一个问题&#xff0c;给定一个长度为n的数组a&#xff0c;他们想要找出符合特定条件的三元组 (i, j, k)。具体来说&#xff0c;三元组要满足 0 < i < j < k < n&#xff0c;并且 max(a[i], a[…

wsl虚拟机中的dockers容器访问不了物理主机

1 首先保证wsl虚拟机能够访问宿主机IP地址&#xff0c;wsl虚拟机通过vEthernet (WSL)的地址访问&#xff0c;着意味着容器也要通过此IP地址访问物理主机。 2 遇到的问题&#xff1a;wsl虚拟机中安装了docker&#xff0c;用在用到docker容器内的开发环境&#xff0c;但是虚拟机…