二叉树：路径之和 Path Sum
给定一个二叉树与整数sum，找出所有从根节点到叶结点的路径，这些路 径上的节点值累加和为sum
即创建一个二叉树，要求二叉树中有一个路径从根节点到叶节点到路径加起来代表到和为 给定的sum
如下二叉树
给定路径之和为18，则需要输出两条路径：
[1,4,5,8]
[1,4,6,7]
同样，这个过程我们可以使用先序深度优先搜索，同时需要使用临时数据结构保存搜索过程中出现的根节点，方便回溯。
实现过程如下:
void getpath(Tree *root, int &path_value, int num, std::vector<int> &path, std::vector<std::vector<int> > &result) {if (root == NULL) {return;}/*搜索的过程中计算和*/path_value += root->data;path.push_back(root->data);/*当访问到了叶子节点，且满足和为sum时，将最终的路径path加入到路径列表*/if (root -> left == NULL && root ->left == NULL && path_value == num) {result.push_back(path);}else if (path_value > num) { //剪枝，当当前路径之和已经大于sum,后面肯定也不存在了，所以后序当前节点的子节点遍历就没有必要了path_value -= root -> data;path.pop_back();}/*搜索左孩子*/getpath(root->left, path_value, num, path, result);/*搜索右孩子*/getpath(root->right, path_value, num, path, result);path_value -= root ->data;path.pop_back();
}
/*初始化并获取返回值*/
std::vector<std::vector<int>> pathSum(Tree *root, int num) {std::vector<std::vector<int>> result;std::vector<int> path;int path_value = 0;getpath(root,path_value, num, path ,result);return result;
}
测试代码如下:
#include <iostream>
#include <stack>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>using namespace std;typedef struct tree
{int data;struct tree *left;struct tree *right;
}Tree,*TreeNode;/*创建二叉树*/
void createTree(TreeNode *root) {char val = 0;cin >> val;if (val == '*') {(*root) = NULL;} else {(*root) = (Tree *)malloc(sizeof(tree));if ((*root) == NULL) {cout << "create node failed " << endl;exit(-1);} else {(*root)->data = val - '0';createTree(&(*root)->left);createTree(&(*root)->right);}}
}
/*获取指定和为sum的路径*/
void getpath(Tree *root, int &path_value, int num, std::vector<int> &path, std::vector<std::vector<int> > &result) {if (root == NULL) {return;}path_value += root->data;path.push_back(root->data);if (root -> left == NULL && root ->left == NULL && path_value == num) {result.push_back(path);} else if (path_value > num) {path_value -= root -> data;path.pop_back();}getpath(root->left, path_value, num, path, result);getpath(root->right, path_value, num, path, result);path_value -= root ->data;path.pop_back();
}
/*初始化路径*/
std::vector<std::vector<int>> pathSum(Tree *root, int num) {std::vector<std::vector<int>> result;std::vector<int> path;int path_value = 0;getpath(root,path_value, num, path ,result);return result;
}int main(int argc, char const *argv[])
{/* code */TreeNode root;cout << "construct the tree " << endl;createTree(&root);cout << "input sum path " << endl;int num;cin >> num;cout << "sum path is " << endl;std::vector<std::vector<int> > result;result = pathSum(root, num);for (int i = 0;i < result.size(); ++i) {for (int j = 0;j < result[i].size(); ++j) {cout << "[" << result[i][j] << "] ";}cout << endl;}return 0;
}
输出如下:
#输入：构造文章开头的二叉树
construct the tree
123***458***67***
input sum path
18#输出路径
sum path is
[1] [4] [5] [8]
[1] [4] [6] [7]
相关文章：
从零开始编写自己的C#框架（16）——Web层后端父类
从零开始编写自己的C#框架（16）——Web层后端父类 原文:从零开始编写自己的C#框架（16）——Web层后端父类 本章节讲述的各个类是后端系统的核心之一，涉及到系统安全验证、操作日志记录、页面与按键权限控制、后端页面功能…
c语言中的普通字符包括什么,【判断题】C语言中的字符常量通常有两种形式:普通字符和转义字符。...
【判断题】C语言中的字符常量通常有两种形式:普通字符和转义字符。更多相关问题－－－Can you speak French？－－－Yes, but only____.A．a littleB．littleC．muchD&a…
Codeforces Round #104 (Div. 2) E DP(01背包模型) +组和+除法取模求逆元
题意： 规定只包含4或7的数为幸运数字，给定n个数的序列，求他的子序列，使得该子序列的长度为k并且满足该子序列中不存在相同的两个幸运数字。问一共寻在多少种可能。（只要该数的下标不同则认为是不同的序列） …
django 增加验证邮箱功能
在user文件夹下新建python包，utils 在包内新建文件email_send.py,其中包括验证字符串随机码的产生，数据库的存储和email的发送 # -*- coding: utf-8 -*- # 作者：神秘藏宝室 # 日期：2019/1/1 22:21 from random import Random from…
二叉树：最近的公共祖先 Lowest Common Ancestor of a Binary Tree
已知二叉树，求二叉树中给定的两个节点的最近公共祖先。 最近公共祖先: 两节点v与w的最近公共祖先u，满足在树上最低(离根最 远)，且v,w两个节点都是u的子孙。 如上二叉树，6和8号节点的公共祖先有4，1；但是最近…
VS不显示最近打开的项目
VS2012不显示最近打开的项目 解决方法， 在"运行"中输入 " gpedit.msc"打开后在"用户配置"-"管理模板"-"任务栏和开始菜单" 然后将用户配置-->管理模板-->不保留最近打开文档的历史 将此选项设置为禁用 源…
河科大c语言上机实验答案,2016年河南科技学院信息工程学院C语言上机编程考研复试题库...
一、选择题1． 以下选项中，能用作数据常量的是( )。答:D【解析】A 项错误，十六进制数用数学0和字符x (或大写字母X )开头；B 项错误，八进制整数常量以数字0开始，有效数字为0〜7; C项错误，C 语言中…
无符号数溢出之后
2019独角兽企业重金招聘Python工程师标准>>> [rootcentos ~]# cat test.c #include <stdio.h>int main() {unsigned short i 0x0;while(1){printf("%u \n",i);if(i 0) //溢出之后 又会回到 0 所以不会 死循环break;} } 转载于:https://my.oschin…
加载BeanFactory
前言 上一篇文章讲述了ApplicationContext扩展功能的之一：环境准备。这篇文章接着讲述ApplicationContext的扩展功能-----加载BeanFactory，也就是初始化BeanFactory，并进行XML文件的读取。 加载BeanFactory obtainFreshBeanFactory方法从字面…
t-top 命令详解
前言 展示操作系统进程信息。动态得，实时得展示正在运行的操作系统进程信息。 所显示的系统摘要信息的类型以及为进程显示的信息的类型，顺序和大小都是用户可配置的，并且可以使配置在重新启动后保持不变。该程序为流程操作提供了一个有限的交…
怎么看懂c语言程序,求讲解一下这个程序，我看了1个小时都没有看懂，
该楼层疑似违规已被系统折叠 隐藏此楼查看此楼# include #define N 9void fun(int a[], int n){ int i,j, max, min, px, pn, t;for (i0; i{/**********found**********/max min ___a[i]__;px pn i;for (ji1; j/**********found**********/if (max<___a>{ max a[j];…
【转】Winform输入法控制
来源：http://blog.itpub.net/23109131/viewspace-630576 想实现输入法切换：思路，找出当前系统所有输入法总个数，当前输入法在总输入法中的索引，通过改变索引值，来切换输入法 void input() {//变全角为半角的…
vector与结构体联合使用 在磁盘中生成.txt 文件
一下纯属个人总结、欢迎拍砖！谢谢 我意思到以练促进学习C编程基础是很有帮助的 这篇文章是我为了熟悉掌握文件流和STL中的vector以及结构体三个只知识点所写的代码： #include <string> #include <stdlib.h> #include <iostream> #incl…
SQL Server 2008 R2如何开启数据库的远程连接
SQL Server 2008 R2如何开启数据库的远程连接 转载于:https://www.cnblogs.com/macT/p/10213025.html
二分法：二分查找（递归+非递归）实现
二分查找又称折半查找，首先，假设表中元素是按升序排列，将 表中间位置的关键字与查找关键字比较: 如果两者相等，则查找成功;否则利用中间位置将表分成前、后两个子表: 1)如果中间位置的关键字大于查找关键字，则进一步查…
mongodb数据库的一些常用命令列表
超级用户相关：use admin#增加或修改用户密码db.addUser(ixigua,pwd)#查看用户列表db.system.users.find()#用户认证db.auth(ixigua,pwd)#删除用户db.removeUser(mongodb)#查看所有用户show users#查看所有数据库show dbs#查看所有的collectionshow collections#查看…
c语言函数库哪里keyk,[精品]C语言库函数(字母G-K)-教案.doc
[精品]C语言库函数(字母G-K)-教案C语言库函数(字母G-K)- -??????????????????????????????????????(G类字母) - 1函数名: gcvt 功 能: 把浮点数转换成字符串 用 法: char *gcvt(double value, int ndigit, char *buf); 程序例: #include…
超链接调用js函数
<a href"javascript:gouwu()" ><span class"Buy" id"buyButton"></span></a>超链接调用js前面要加javascript:****************************SuppressWarningsJ2SE 提供的最后一个批注是 SuppressWarnings。该批注的作用…
iOS 轻击、触摸和手势的检测
一、检测捏合手势( UIPinchGestureRecognizer): //设定一个实例变量存储手指之间的其起始距离 property (assign, nonatomic) CGFloat initialFontSize;//调用：UIPinchGestureRecognizer *pinch [[UIPinchGestureRecognizeralloc]initWithTarget:selfaction:select…
二分法：search insert position 插入位置
问题描述： 给定一个排序数组nums(无重复元素)与目标值target，如果target在nums里 出现，则返回target所在下标，如果target在nums里未出现，则返回target应该 插入位置的数组下标，使得将target插入数组nums后&…
c语言课程设计学生籍贯信息记录簿,C语言课程设计 学生籍贯信息记录簿设计.doc...
C语言与程序设计课程设计学生籍贯信息记录簿设计学 院 信息工程班 级 物联1301班学 号 131408119姓 名 滕玲一．设计目的该软件主要是编辑一个学生籍贯信息记录簿记录每个学生信息，包括：学号、姓名、籍贯。具体功能：1.创建信息链表…
SharePoint使用BCS开发你第一个应用程序（三）
SharePoint使用BCS开发你第一个应用程序（三） 创建外部内容类型。 创建外部内容类型有三种不同方式：1. 在记事本上手写XML代码（不推荐）。2. 使用SharePoint Designer 2010 创建（推荐）。3. 使用VS…
Java Coverage(Cobertura)工具
首先是下载Cobertura的jar包了，这个工具底层是JCoverage，熟悉Jcoverage的对这个也不会陌生的。 Cobertura官网 http://cobertura.sourceforge.net/ 大家可以了解很多东西，比如现在的作者啊什么，这里就不介绍了 然后点Download&…
Java 内部类及其原理
Java中实现内部类 内部类相信大家都用过很多次了，就不说它是怎么用的了。 内部类 1.成员内部类 需要注意的是， 当成员内部类拥有和外部类同名的成员变量或这方法时， 默认情况下访问的是内部类的成员， 如要访问外部类的同名成员&am…
二分法：查找区间search for a range
问题描述： 给定一个排序数组nums(nums中有重复元素)与目标值target，如果 target在nums里出现，则返回target所在区间的左右端点下标，[左端点, 右端点]，如果target在nums里未出现，则返回[-1, -1]。 例如: ar…
c语言向表格内存入数据,怎么实现横向到存入多个单元格,在列数固定的报表中逐格横向填充数据并折行...
在很多需要打印的报表中，受限于纸张的大小，往往会限制行数或者固定列数。我们在《单据类报表的制作》一文中，曾经介绍了限制了行数的情况如何实现，现在，我们再来看一下，在固定了列数的情况下，如…
设计模式之简单工厂模式
一、概述 工厂模式具体包括了简单工厂、工厂方法、抽象工厂，它们是按照从简单到复杂的顺序排列的，属于设计模式中的创建型，其中简单工厂并不属于GOF的23中模式。 但是它是理解其它的工厂模式的一个很好的基础，所以很多人在讲述设…
zendserver的版本是怎么回事？免费版哪里去了？
zend server 的版本，官网上说是四个版本，免费版、小企业版、专业版、企业版。 但下载只有一个版本。在下载的页面中大大的free download 很是显眼。安装完成之后显示为企业版。使用几天之后，显示你的许可即将到期。 输入密码，登录…
sql-case when 条件1 then 取值1 when 条件2 then 取值2 else 取值3 end
遇到 XXX情况 就 XXX 遇不到就 XXX 结束case when …… then …… else …… end 例如一个3条件取值的字段： case when 条件1 then 取值1 when 条件2 then 取值2 else 取值3 end when后接条件语句，then后为字段取值（数值或字符串等都可以&…
二叉树：二叉搜索树的创建和插入
二叉搜索树又名二叉排序树。 大概简略的思维导图如下，方便记忆特性 基本二叉搜索树创建过程如下 /*数据结构如下*/ typedef struct tree {int data;struct tree *left NULL;struct tree *right NULL; }Tree,*TreeNode;/*Node 为二叉树根节点，insert…