題目:輸入一個(gè)整數(shù)和一棵二元樹(shù)换途。 從樹(shù)的根結(jié)點(diǎn)開(kāi)始往下訪(fǎng)問(wèn)一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的所有結(jié)點(diǎn)形成一條路徑掀潮。 打印出和與輸入整數(shù)相等的所有路徑。
例如輸入整數(shù) 22 和如下二元樹(shù)
10
/
5 12
/ \
4 7
則打印出兩條路徑:10, 12 和 10, 5, 7
hint: 借助 數(shù)組 模擬 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;
}
