首页 > 代码库 > 二叉树中和为某一值的路径

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

2024-07-15 16:34:22   217人阅读

题目：输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

比如：


上面这棵二叉树，如果寻找和为22的路径，那应该有两条，首先是10,5,7，另外一条是10,12.

思路：
可以按照先序遍历的方式访问二叉树，这样可以确保根先于子树被访问到，另外需准备一个栈（可用数组代替，因为需要打印路径），每访问一个结点，就统计当前路径和以及当前结点是否是叶子结点，如果满足则打印，否则递归其左右子树，需要注意的是在返回到父节点时，需要将栈顶元素删除。

代码：
/*
二叉树中和为某一值的路径
by Rowandjj
2014/8/4
*/
#include<stdio.h>
#include<stdlib.h>
#define MAX 1000
typedef struct _NODE_
{
	int data;
	struct _NODE_ *lChild;
	struct _NODE_ *rChild;
}Node,*pNode,*pTree;
void FindPath(pTree pT,int stack[],int exceptedNum,int curNum,int p)
{
	curNum += pT->data;//路径和加上当前结点值
	stack[p++] = pT->data;//把当前结点纳入stack中
	bool isLeaf = (pT->lChild == NULL) && (pT->rChild == NULL);//是否为叶子结点
	if((curNum == exceptedNum) && isLeaf)//当前为叶子节点而且路径和恰为期待值
	{
		printf("found a path:");
		for(int i = 0; i < p; i++)//打印路径
		{
			printf("%d ",stack[i]);
		}
		printf("\n");
	}
	
	if(pT->lChild)//如果有左孩子,那么递归遍历左子树
	{
		FindPath(pT->lChild,stack,exceptedNum,curNum,p);
	}
	if(pT->rChild)//如果有右孩子
	{
		FindPath(pT->rChild,stack,exceptedNum,curNum,p);
	}
	p--;//返回父节点前要将栈回退,pop出当前栈顶元素
}
void FindPath(pTree pT,int exceptedNum)
{
	int stack[1000];//使用数组模拟一个栈
	if(pT == NULL)
	{
		return;
	}
	int curNum = 0;//当前路径和
	int p = 0;//栈顶指针
	FindPath(pT,stack,exceptedNum,curNum,p);
}	
void create(pTree *ppTree)
{
	int data;
	scanf("%d",&data);
	if(data =http://www.mamicode.com/= -1)>
看OJ上这道题：
题目描述：
输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
输入：
每个测试案例包括n+1行：
第一行为2个整数n，k(1<=n<=10000)，n表示结点的个数，k表示要求的路径和，结点编号从1到n。                                                                                                       
接下来有n行。这n行中每行为3个整数vi,leftnode,rightnode，vi表示第i个结点的值，leftnode表示第i个结点的左孩子结点编号，rightnode表示第i个结点的右孩子结点编号，若无结点值为-1。编号为1的结点为根结点。
输出：
对应每个测试案例，先输出“result:”占一行，接下来按字典顺序输出满足条件的所有路径，这些路径由结点编号组成，输出格式参照输出样例。
样例输入：
5 2210 2 35 4 512 -1 -14 -1 -17 -1 -11 51 -1 -1
样例输出：
result:A path is found: 1 2 5A path is found: 1 3result:
注意两点：
1.输出的是结点的序号，而不是结点值；
2.以字典顺序输出；

很显然，我们应该使用数组来存储二叉树:
代码：
#include<stdio.h>
#include<stdlib.h>
#define MAX 100000
typedef struct _NODE_
{
	int data;
	int lChild;
	int rChild;
	int index;
}Node,*pNode;
void FindPath(pNode pTree,int exceptedNum,int curNum,int stack[],int p,int index)
{//exceptedNum为期待路径和,curNum为当前路径和，stack为栈数组，p为栈顶指针，index为当前
树根的位置
	if(pTree == NULL || index == -1)
	{
		return;
	}
	curNum += pTree[index].data;
	stack[p++] = pTree[index].index;
	
	bool isLeaf = (pTree[index].lChild == -1) && (pTree[index].rChild == -1);
	if(isLeaf && (curNum == exceptedNum))
	{
		printf("A path is found:");
		for(int i = 0; i < p; i++)
		{
			printf(" %d",stack[i]);	
		}
		printf("\n");
	}
	if(pTree[index].lChild < pTree[index].rChild)
	{
		FindPath(pTree,exceptedNum,curNum,stack,p,pTree[index].lChild);
		FindPath(pTree,exceptedNum,curNum,stack,p,pTree[index].rChild);
	}else
	{
		FindPath(pTree,exceptedNum,curNum,stack,p,pTree[index].rChild);
		FindPath(pTree,exceptedNum,curNum,stack,p,pTree[index].lChild);
	}
	p--;
}
void FindPath(pNode pTree,int exceptedNum)
{
	if(pTree == NULL)
	{
		return;
	}
	int cutNum = 0;
	int p = 0;
	int stack[MAX];
	int index = 0;
	FindPath(pTree,exceptedNum,cutNum,stack,p,index);
}
int main()
{
	int n,k;
	while(scanf("%d %d",&n,&k) != EOF)
	{
		if(n <= 0)
		{
			continue;
		}
		pNode pTree = (pNode)malloc(sizeof(Node)*n);
		if(!pTree)
		{
			exit(-1);
		}
		for(int i = 0; i < n; i++)
		{
			int data,left,right;
			scanf("%d %d %d",&data,&left,&right);
			pTree[i].data = http://www.mamicode.com/data;>


联系
我们