描述:
请写一个程序创建一棵二叉树，并按照一定规则，输出二叉树根节点到叶子节点的路径。
规则如下：
1、从最顶端的根结点，到最下面的叶子节点，计算路径通过的所有节点的和，如果与设置的某一值的相同，那么输出这条路径上的所有节点。
2、从根节点遍历树时，请请按照左到右遍历，即优先访问左子树的节点。
二叉树创建规则：从上到下一层一层的，按照从左到右的顺序进行构造
输入”10,5,12,4,7″值，构造的树如下：
1） 10
2） 10
/
5
3） 10
/\
5 12
4） 10
/\
5 12
/
4
5） 10
/\
5 12
/\
4 7
针对上面的二叉树，如果当前我们设置的“路径和”为19，那么输出结果为:
10,5,4
如果有多个路径，按到左到右的顺序遍历生成的结果每行显示一个显示。例如如果当前我们设置的“路径和”为22，那么输出结果为:
10,5,7
10,12
如果没有找到路径和为设置的值的路径，输出error。
运行时间限制: 无限制
内存限制: 无限制
输入:
输入整数N—路径和
一行字符串，多个正整数，之间用”,”隔开
输出:
满足条件的二叉树路径
样例输入:
22
10,5,12,4,7
样例输出:
10,5,7
10,12
答案提示:
首先是建树，这个由于是按照节点序来建，故必须要知道父节点与子节点即2n＋1 与2n＋2的关系。
树建立后，深度优先，找到小于当前的将路径压站，相等了弹出打印，不相等接着递归。
#include
#include
#include
#include
using namespace std;
bool myfind = false;
struct TreeNode
{
int data;
TreeNode* pLeftChild;
TreeNode* pRightChild;
};
void creatnode(TreeNode*&root, vector
{
if(i >= len)
return;
root = new TreeNode;
root->data = a[i];
root->pLeftChild = NULL;
root->pRightChild = NULL;
creatnode(root->pLeftChild, a, 2*i + 1, len);
creatnode(root->pRightChild, a, 2*i + 2, len);
}
void CreateTree(TreeNode* &pRoot)
{
vector
char *buffer = new char[3000];
memset(buffer, 0, 3000);
cin>>buffer;
char *but = new char[10];
memset(but, 0, 10);
int i = 0;
int k = 0;
while(buffer[i]!=0)
{
if(buffer[i]!=',')
{
but[k]=buffer[i];
k++;
}
else
{
int a = atoi(but);
memset(but, 0, 10);
num.push_back(a);
k=0;
}
i++;
}
int a = atoi(but);
num.push_back(a);
k=0;
creatnode(pRoot, num, 0, num.size());
}
void PrintPath(TreeNode* pRoot, int sum, const int target)
{
static deque
if(pRoot == NULL) return;
if(sum + pRoot->data == target)// 如果当前值加上路径和为目标值，则输出
{
myfind = true;
for(int i=0; i
{
return;
}
else// 如果小于，则入栈
{
stack.push_back(pRoot->data);
sum += pRoot->data;
PrintPath(pRoot->pLeftChild, sum, target);
PrintPath(pRoot->pRightChild,sum,target);
sum -= pRoot->data;
stack.pop_back();
}
}
int main()
{
int num = 0;
cin >> num;
TreeNode* pTree = NULL;
CreateTree(pTree);
PrintPath(pTree, 0, num);
if(!myfind)
{
cout<<"error";
}
}