面试100题004--二元树中找出和为某一值的所有路径

2023-12-23 10:38

本文主要是介绍面试100题004--二元树中找出和为某一值的所有路径,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一刷100题的第三天。

题目:输入一个整数和一棵二元树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
例如 输入整数22和如下二元树
  10   
  / /   
  5 12   
  / /   
  4 7
则打印出两条路径:10, 12和10, 5, 7。

二元树节点的数据结构定义为:

struct BinaryTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BinaryTreeNode *m_pLeft; // left child of node
BinaryTreeNode *m_pRight; // right child of node
};

答案:

#include <iostream>
#include <vector>
using namespace std;
struct BSTreeNode {
int m_nvalue;
BSTreeNode *m_pleft;
BSTreeNode *m_pright;
};
void addBSTreeNode(BSTreeNode * & pCurrent, int value) {
if (pCurrent == NULL) {
BSTreeNode *pBSTree = new BSTreeNode();
pBSTree->m_nvalue = value;
pBSTree->m_pleft = NULL;
pBSTree->m_pright = NULL;
pCurrent = pBSTree;
}
else {
if (pCurrent->m_nvalue > value) {
addBSTreeNode(pCurrent->m_pleft, value);
}
else if (pCurrent->m_nvalue < value) {
addBSTreeNode(pCurrent->m_pright, value);
}
else {
cout << "this tree has this number!" << endl;
}
}
}
void findPath(BSTreeNode * & pCurrent, int expectedSum, std::vector<int> &path,int &currentSum) {
if (!pCurrent) {
return;
}
currentSum += pCurrent->m_nvalue;
path.push_back(pCurrent->m_nvalue);
bool isLeaf = (!pCurrent->m_pleft&&!pCurrent->m_pright);
if (currentSum == expectedSum&&isLeaf) {
std::vector<int>::iterator iter = path.begin();
for (; iter != path.end();iter++) {
std::cout << *iter << '\t';
}
std::cout << std::endl;
}
if (pCurrent->m_pleft) {
findPath(pCurrent->m_pleft, expectedSum, path,currentSum);
}
if (pCurrent->m_pright) {
findPath(pCurrent->m_pright, expectedSum, path,currentSum);
}
currentSum -= pCurrent->m_nvalue;
path.pop_back();
}
int main() {
BSTreeNode *pRoot = NULL;
addBSTreeNode(pRoot, 10);
addBSTreeNode(pRoot, 5);
addBSTreeNode(pRoot, 4);
addBSTreeNode(pRoot, 7);
addBSTreeNode(pRoot, 12);
std::vector<int> path;
int currentSum = 0;
int expectedSum = 19;
findPath(pRoot, expectedSum, path, currentSum);
return 0;
}


总结:完全是跟着July的答案写的。鄙视自己一下。一开始看明白了自己写一下还各种出错,最后直接把一些部分复制粘贴了,鄙视自己一下。。最后发现原来是查找树的建立操作是先序遍历的,在主函数里添加数字加反了,晕死。。。

今天新学了vector容器,用法太多还不太熟。

希望能够坚持 慢慢进步吧。。。

这篇关于面试100题004--二元树中找出和为某一值的所有路径的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

Python打印对象所有属性和值的方法小结

《Python打印对象所有属性和值的方法小结》在Python开发过程中,调试代码时经常需要查看对象的当前状态,也就是对象的所有属性和对应的值,然而,Python并没有像PHP的print_r那样直接提... 目录python中打印对象所有属性和值的方法实现步骤1. 使用vars()和pprint()2. 使

Python pip下载包及所有依赖到指定文件夹的步骤说明

《Pythonpip下载包及所有依赖到指定文件夹的步骤说明》为了方便开发和部署,我们常常需要将Python项目所依赖的第三方包导出到本地文件夹中,:本文主要介绍Pythonpip下载包及所有依... 目录步骤说明命令格式示例参数说明离线安装方法注意事项总结要使用pip下载包及其所有依赖到指定文件夹,请按照以

SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志

《SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志》在SpringBoot项目中,使用logback-spring.xml配置屏蔽特定路径的日志有两种常用方式,文中的... 目录方案一:基础配置(直接关闭目标路径日志)方案二:结合 Spring Profile 按环境屏蔽关

VSCode设置python SDK路径的实现步骤

《VSCode设置pythonSDK路径的实现步骤》本文主要介绍了VSCode设置pythonSDK路径的实现步骤,包括命令面板切换、settings.json配置、环境变量及虚拟环境处理,具有一定... 目录一、通过命令面板快速切换(推荐方法)二、通过 settings.json 配置(项目级/全局)三、

使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)

《使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)》字体设计和矢量图形处理是编程中一个有趣且实用的领域,通过Python的matplotlib库,我们可以轻松将字体轮廓... 目录背景知识字体轮廓的表示实现步骤1. 安装依赖库2. 准备数据3. 解析路径指令4. 绘制图形关键

如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)

《如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)》:本文主要介绍如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)问题,具有很好的参考价值,希望对大家有所帮助,如有... 目录先在你打算存放的地方建四个文件夹更改这四个路径就可以修改默认虚拟内存分页js文件的位置接下来从高级-

一文详解如何查看本地MySQL的安装路径

《一文详解如何查看本地MySQL的安装路径》本地安装MySQL对于初学者或者开发人员来说是一项基础技能,但在安装过程中可能会遇到各种问题,:本文主要介绍如何查看本地MySQL安装路径的相关资料,需... 目录1. 如何查看本地mysql的安装路径1.1. 方法1:通过查询本地服务1.2. 方法2:通过MyS

Python如何调用指定路径的模块

《Python如何调用指定路径的模块》要在Python中调用指定路径的模块,可以使用sys.path.append,importlib.util.spec_from_file_location和exe... 目录一、sys.path.append() 方法1. 方法简介2. 使用示例3. 注意事项二、imp

使用Python实现矢量路径的压缩、解压与可视化

《使用Python实现矢量路径的压缩、解压与可视化》在图形设计和Web开发中,矢量路径数据的高效存储与传输至关重要,本文将通过一个Python示例,展示如何将复杂的矢量路径命令序列压缩为JSON格式,... 目录引言核心功能概述1. 路径命令解析2. 路径数据压缩3. 路径数据解压4. 可视化代码实现详解1

数据库面试必备之MySQL中的乐观锁与悲观锁

《数据库面试必备之MySQL中的乐观锁与悲观锁》:本文主要介绍数据库面试必备之MySQL中乐观锁与悲观锁的相关资料,乐观锁适用于读多写少的场景,通过版本号检查避免冲突,而悲观锁适用于写多读少且对数... 目录一、引言二、乐观锁(一)原理(二)应用场景(三)示例代码三、悲观锁(一)原理(二)应用场景(三)示例