题目:输入一个整数和一棵二元树。 从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。 打印出和与输入整数相等的所有路径。
例如输入整数 22 和如下二元树
10
/
5 12
/ \
4 7
则打印出两条路径:10, 12 和 10, 5, 7
hint: 借助 数组 模拟 Stack
#include <iostream>
#include <string>
using namespace std;
struct BSTreeNode
{
int value;
BSTreeNode *left;
BSTreeNode *right;
};
void AddBSTreeNode(BSTreeNode * &pCurrent,int value){
if (NULL==pCurrent) {
BSTreeNode * newNode = new BSTreeNode;
newNode->left=NULL;
newNode->right=NULL;
newNode->value = value;
pCurrent = newNode;
}else{
if (pCurrent->value>value) {
AddBSTreeNode(pCurrent->left, value);
}else if (pCurrent->value<value)
AddBSTreeNode(pCurrent->right, value);
}
}
void printPath(int path[],int size){
for (int i=0; i<size ; i++) {
cout<<path[i]<<endl;
}
cout<<endl;
}
void printRoute(BSTreeNode *root,int sum,int path[],int top){
path[top++]=root->value;
sum-=root->value;
if (root->left==NULL&&root->right==NULL) {
if (sum==0) {
printPath(path,top);
}
}else{
if (root->left!=NULL)
printRoute(root->left, sum, path, top);
if (root->right!=NULL)
printRoute(root->right, sum, path, top);
}
top--;
sum+=root->value;
}
int main()
{
BSTreeNode * root = NULL;
AddBSTreeNode(root, 10);
AddBSTreeNode(root, 5);
AddBSTreeNode(root, 4);
AddBSTreeNode(root, 7);
AddBSTreeNode(root, 12);
int path[100];
printRoute(root, 22, path, 0);
return 0;
}
