题目描述:
输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
输入:
每个测试案例包括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 22
10 2 3
5 4 5
12 -1 -1
4 -1 -1
7 -1 -1
1 5
1 -1 -1
样例输出:
result:
A path is found: 1 25
A path is found: 1 3
result:
#include<stdio.h>
#include<stdlib.h>
#define MAX 1000
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
int top=-1;
int path[MAX];//用数组模拟辅助栈
//pop 使得top--
bool pop()
{
if(top<0)
return false;
top--;
return true;
}
void findPath(BinaryTreeNode* pRoot,int expectSum,int currentSum)
{
if(pRoot==NULL)
return;
currentSum+=pRoot->m_nValue;
path[++top]=pRoot->m_nValue;
bool isLeaf =pRoot->m_pLeft==NULL&&pRoot->m_pRight==NULL;
if(currentSum==expectSum&&isLeaf)
{
printf("A path is found:");
for(int i=0;i<=top;i++)
printf("%d\t",path[i]);
printf("\n");
}
if(pRoot->m_pLeft!=NULL)
findPath(pRoot->m_pLeft,expectSum,currentSum);
if(pRoot->m_pRight!=NULL)
findPath(pRoot->m_pRight,expectSum,currentSum);
currentSum-=pRoot->m_nValue;
pop();
}
BinaryTreeNode* createTree(BinaryTreeNode* pRoot)
{
int data;
scanf("%d",&data);
if(data!=-1)
{
pRoot=(BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
if(pRoot==NULL)
exit(0);
pRoot->m_nValue=data;
//递归左子树和右子树
pRoot->m_pLeft=createTree(pRoot->m_pLeft);
pRoot->m_pRight=createTree(pRoot->m_pRight);
return pRoot;
}
return NULL;
}
int main()
{
BinaryTreeNode* pTree;
BinaryTreeNode* pRoot = createTree(pTree);
int expectSum;
int currentSum=0;
scanf("%d",&expectSum);
findPath(pRoot,expectSum,currentSum);
return 0;
}
结果:
分享到:
相关推荐
二叉树中和为某一值的路径.md
32.二叉树中和为某一值的路径1
java基础面试题二叉树中和为某一值的路径本资源系百度网盘分享地址
34. 二叉树中和为某一值的路径题目描述输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。下图的二叉树有两条和为 22 的路径:10, 5
Leetcode 面试题 34 二叉树中和为某一值的路径题目描述输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直
示例:给定如下二叉树,以及目标和 sum = 22,返回:* Definition for a binary tree node.vector<vector<i
题目输入一颗二叉树的根节点和一个整数,按字典序打印出二叉树中结点值的和为输入整数的所有路径路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径示例
输入一颗二叉树的根节点和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。路径定义为从树的根节点开始往下已知到叶节点所经过的节点所形成的一条路径。在返回值的list中,数组长度大的数组靠前。 class ...
输入一棵二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。输出:[[5,4,12,1],[5,6,6,5]]private List> res =
二叉树中和为某一值的路径: 输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中,...
剑指Offer(Python多种思路实现):二叉树中和为某一值的路径 面试34题: 题目:二叉树中和为某一值的路径 题:输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始...
# Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...
示例:给定如下二叉树,以及目标和 sum = 22,返回:思路套用回溯算法的思路设定一个结果数组result来存储所有符合条件的路径设定一个栈stack来存储当
主要介绍了Python编程求解二叉树中和为某一值的路径代码示例,具有一定借鉴价值,需要的朋友可以参考下
主要介绍了C++实现查找二叉树中和为某一值的所有路径的示例,文中的方法是根据数组生成二叉排序树并进行遍历,需要的朋友可以参考下
从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。 例如: 给定二叉树: [3,9,20,null,null,15,7], 返回: [3,9,20,15,7] 解题思路:先进先出,队列的思想 从上到下打印二叉树的规律:每一次打印...
输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。 原创文章 269获赞 703访问量 3万+ 关注 私信 展开阅读全文 作者:...
主要介绍了python3实现在二叉树中找出和为某一值的所有路径,本文通过一个实例demo给大家介绍的非常详细,具有一定的参考借鉴价值,需要的朋友可以参考下