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

程序员面试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 leaf
	bool 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;
}