# 求二叉树中和为给定值的所有路径

You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree-it does not have to start at the root.

```#include <algorithm>
#include <iostream>
#include <time.h>
#include <assert.h>
#include <stdio.h>
#include <vector>

using namespace std;

struct node
{
int data;
struct node * lchild;
struct node * rchild;
};

//将数组转换为深度最低的二叉树，采用了二分查找的思想
struct node* ConvertArrayToTree(int data[], int first, int last)
{
if (last < first)
{
return NULL;
}
else
{
int mid = ( last + first ) / 2;
struct node * newNode = NULL;
newNode = (struct node *)malloc(sizeof(struct node));
newNode->data = data[mid];
newNode->lchild = ConvertArrayToTree(data, first, mid - 1);
newNode->rchild = ConvertArrayToTree(data, mid + 1, last);
return newNode;
}
}

//再最左边插入一个节点
void InsertNodeAtLeft(struct node *root, struct node *newNode)
{
assert(root != NULL && newNode != NULL);
while(root->lchild != NULL)
{
root = root->lchild;
}
root->lchild = newNode;
}

//在最右边插入一个节点
void InsertNodeAtRight(struct node *root, struct node *newNode)
{
assert(root != NULL && newNode != NULL);
while(root->rchild != NULL)
{
root = root->rchild;
}
root->rchild = newNode;
}
//中序遍历
void Traverse(struct node *root)
{
if (root == NULL)
{
return;
}
Traverse(root->lchild);
Traverse(root->rchild);
printf("%d\t", root->data);
}

//打印和为sum的路径
void print(vector<int>& buffer, int first, int last)
{
int i;
for (i = first; i <= last; i++)
{
cout << buffer[i] << "\t";
}
cout << endl;
}
void findSum(struct node *head, int sum, vector<int> &buffer, int level)
{

int i;
int tmp = sum;
for (i = level; i >= 0; i--)
{
tmp -= buffer[i];
if (tmp == 0) print(buffer, i, level);
}

vector<int> lbuffer(buffer);
vector<int> rbuffer(buffer);

findSum(head->lchild, sum, lbuffer, level + 1);
findSum(head->rchild, sum, rbuffer, level + 1);
}

int main(int argc, char* argv[])
{
const int SIZE = 10;//测试的数据量
int data[SIZE];//保存数据
int i, j;

for (i = 0; i < SIZE; i++)
{
data[i] = i + 1;
}

head = ConvertArrayToTree(data, 0, SIZE - 1);

struct node *one = (struct node *)malloc(sizeof(struct node));
struct node *two = (struct node *)malloc(sizeof(struct node));
one->data = 11;
one->lchild = NULL;
one->rchild = NULL;

two->data = 4;
two->lchild = NULL;
two->rchild = NULL;

//遍历数据
//  printf("\n");
vector<int> v;
return 0;
} ```

## LeetCode | 面试题34. 二叉树中和为某一值的路径【剑指Offer】【Python】

LeetCode 面试题34. 二叉树中和为某一值的路径[剑指Offer][Medium][Python][回溯] 问题 力扣 输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径.从树的根节点开始往下一直到叶节点所经过的节点形成一条路径. 示例: 给定如下二叉树,以及目标和 sum = 22, 5 / 4 8 / / 11 13 4 / \ / 7 2 5 1 返回: [ [5,4,11,2], [5,8,4,5] ] 提示: 节点总数 <= 10000 注意:本题与主站 1

## 求数组中和为给定值的所有子序列

2017年网易游戏的一道编程题,大致意思是满足组合攻击技能,必须是所选择时技能的和为m(m>0),且所选的这些技能的乘积最大: 分解后主解决两个问题: 其一:求数组中和为m的所有子数组: 其二:在满足一的条件下,求所有子数组的最大值: 主要考察的还是如何求数组中和为m的所有子数组: 如:数组[1,2,3,4,5,6],m=7时,满足条件的子数组有[1,2,4],[3,4],[2,5],[1,6]; 主要使用回溯法解决该问题,思路以后补上: import java.util.ArrayList;

## 12 二叉树中和为某一值的路径

0 引言 题目:输入一颗二叉树的根节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径.路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径.(注意: 在返回值的list中,数组长度大的数组靠前) 1 抽象问题具体化 举例1:树的形态如图所示.给定的整数值为22,求路径. 解答:所有的路径总共有三条,分别是 1)10->5->4,和为19: 2)10->5->7,和为22: 3)10->12,和为22. 2 具体问题抽象分析 分三步 1)写出所有的路径: