程序员面试100题(算法)之二叉树中找出和为某一值的所有路径(含二叉树前序创建、遍历)

#include "stdafx.h"#include<iostream>#include<vector>using namespace std;struct binaryTreeNode{binaryTreeNode *leftNode;binaryTreeNode *rightNode;int value;};void findPath(binaryTreeNode *tNode, int sum, vector<int> &path, int ¤tSum){if(!tNode)return;currentSum = currentSum + tNode->value;path.push_back(tNode->value);//if node is a leafbool isLeaf = (!tNode->leftNode) && (!tNode->rightNode);if(currentSum == sum && isLeaf){vector<int>::iterator iter = path.begin();for(; iter != path.end(); iter++){cout << *iter << "\t";}cout << endl;}if(tNode->leftNode)findPath(tNode->leftNode, sum, path, currentSum);if(tNode->rightNode)findPath(tNode->rightNode, sum, path, currentSum);currentSum = currentSum - tNode->value;path.pop_back();}binaryTreeNode* createBiTree(binaryTreeNode *&tNode){int value = 0;cin >> value;if(value == -1){tNode = NULL;}else{tNode = (binaryTreeNode*)malloc(sizeof(binaryTreeNode));if(!tNode){cout << "Out of space!" << endl;return NULL;}else{tNode->value = value;createBiTree(tNode->leftNode);createBiTree(tNode->rightNode);}}return tNode;}void preTraverseBTree(binaryTreeNode *root){   if(root)   {   cout << root->value << "\t";   preTraverseBTree(root->leftNode);   preTraverseBTree(root->rightNode);     }}int _tmain(int argc, _TCHAR* argv[]){int currentSum = 0;int sum = 0;binaryTreeNode* bTree = NULL;vector<int> path;cout << "Create the bianry tree with preorder:" <<endl;cout << "Please enter the integer, -1 means node is empty." <<endl;bTree = createBiTree(bTree);cout << "Print the bianry tree with preorder:" <<endl;preTraverseBTree(bTree);cout << endl;cout << "Please enter the sum:" <<endl;cin >> sum;cout << "All pathes of the bianry tree with sum 22 are as below:" <<endl;findPath(bTree, sum, path, currentSum);return 0;}