首页 > 二叉树：路径之和 Path Sum

二叉树：路径之和 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 
#include 
#include 
#include 
#include 
#include 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]

更多相关：

  • Open3d学习计划—高级篇 7（颜色映射）

    Open3D是一个开源库，支持快速开发和处理3D数据。Open3D在c++和Python中公开了一组精心选择的数据结构和算法。后端是高度优化的，并且是为并行化而设置的。本系列学习计划有Blue同学作为发起人，主要以Open3D官方网站的教程为主进行翻译与实践的学习计划。点云PCL公众号作为免费的3D视觉，点云交流社区，期待有使用Op...

  • shell设置系统环境变量的问题

    业务场景： 我在一个bash脚本中修改了PATH变量的内容，并将其保存到/etc/profile文件中，同时执行了 source /etc/profile 但是当脚本退出时，我发现PATH变量还是没有修改生效，但是，如果我在命令行再直接执行 source /etc/profile 才发现PATH生效了。 请问，这是什么原因呢？...

  • Linux上PHP加入环境变量

    export PATH=$PATH:/usr/local/php/bin 转载于:https://www.cnblogs.com/ttiandeng/p/6554902.html...

  • 环境变量path误删解决办法

    2019独角兽企业重金招聘Python工程师标准>>> 每台计算机安装程序不同，环境变量path会有不同，若误删了环境变量path,可以如下完美解决.   Win+R 输入regedit打开注册表(开始-运行里输入regedit）  找到  HKEY_LOCAL_MACHINESYSTEMControlSet002...

  • 在Ubuntu 12.04 64bit上搭建Crtmpserver视频点播服务

    说明如下： (1)所有操作最好使用root操作，以尽可能避免权限问题 (2)crtmpserver和web服务器apache（Ngnix亦可）被装在同一台服务器上，客户端使用其他PC的桌面浏览器和android手机，下面是测试环境示意图： (3)测试环境位于局域网内，由一台路由器接入联通运营商提供的10M包年网络服务 (...

  • Linux 的内存管理工具和调优参数

    1. free 2. top 3. vmstat 4. slabtop; 5. pmap 6. dmesg 7. /proc/meminfo 8. /proc/sys/vm 目录下的文件 9. sync 10./proc/zoneinfo  11./proc/pagetypeinfo 查看内存工具：1.free free - Dis...

  • 二叉树(C++)：创建，前中后序遍历（递归+非递归），获取叶子节点个数，获取树的高度

    文章目录前言创建二叉树先序遍历中序遍历后序遍历获取叶子节点个数获取树的高度测试代码 前言 现有如下二叉树: 关于二叉树的相关操作，我们能够发现二叉树从根节点到子节点，以及每个中间节点基本都能够拆分为若干个子节点的操作，且每个子节点的操作都和其头节点操作一致。 所以我们针对二叉树的操作都可以使用分治算+回溯/归并算法进行...

  • ceph-deploy rpm包的制作

    今天需要部署一个ceph L 版本12.2.12的环境，无奈最近公司网络无法访问到ceph官网，只能使用之前下载好的ceph-deploy-1.5.39版本，安装上之后一口老血喷了出来，没有mgr的部署选项。 无奈之下只能自己制作一个1.5.38版本的ceph-deploy包，借用从ceph-deploy-1.5.39-0.src....

  • MySQL 解压版创建用户密码

    root 权限进入MySQL： mysql –uroot 查看当前MySQL用户： select user,host from mysql.user;     此处以User为root，Host为localhost的账户为例，将密码改为password的命令：   SET PASSWORD FOR 'root'@'localhost...

  • java 读取excel_Java12POI操作Excel

            Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...

  • C++ 生成随机数

    要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...

  • 基于C++的本征图像分解(Intrinsic Image Decomposition)

    利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 剑指offer：面试题39. 数组中出现次数超过一半的数字

    题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...

  • 剑指offer：面试题33. 二叉搜索树的后序遍历序列

    题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树：      5     /    2   6   /  1   3示例 1： 输入: [1,6,3,2,5] 输出...

©2024 11GX.COM