寻找树中和为定值的所有路径

2016.8.18改
You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree-it does not have to start at the root.
思路：
一层一层的遍历，保存当前节点到根节点的完整路径，然后从当前节点向上扫描，如果找到了当前节点到某个节点的和等于给定值，则输出之。程序对每个节点都需要遍历一遍，还要扫描当前节点到根节点的路径，且需要保存每个节点到根节点的路径，所以时间复杂度为O（nlgn)，空间复杂度为O(nlgn)。

#include<iostream>
#include<assert.h>
#include<vector>
#include<malloc.h>
using namespace std;
struct treeNode
{
    struct treeNode *pLeft,*pRight;
    int p_val;
};
struct treeNode *createShortestTree(int *a,int lo,int hi)//构建高度最小的树  二分查找的方法
{
    if (lo > hi)//注意着里没有等号,这里不能省略，否则段错误
        return NULL;
    else
    {
        int mid = (lo+hi)/2;
        int key = a[mid];
        struct treeNode *pRoot = NULL;
        pRoot = (struct treeNode *)malloc(sizeof(struct treeNode));
        pRoot->p_val = key;
        pRoot->pLeft = createShortestTree(a,lo,mid-1);
        pRoot->pRight = createShortestTree(a,mid+1,hi);
        return pRoot;
    }
}
void insetLastLeft(struct treeNode *&pRoot,struct treeNode *pNew)
{
        assert(pRoot != NULL && pNew != NULL);
        struct treeNode *root = pRoot;
        while (root->pLeft)
        {
            root = root->pLeft;
        }
        root->pLeft = pNew;
}
void insertLastRight(struct treeNode *&pRoot,struct treeNode *pNew)
{
    assert(pRoot != NULL && pNew != NULL);//这里别忘了判断pNew
    struct treeNode *root = pRoot;
    while (root->pRight)
    {
        root = root->pRight;
    }
    root->pRight = pNew;
}
void print(vector<int> buffer,int first,int last)//顺序打印
{
    for (int i = first;i <= last;i++)
    {
        cout << buffer[i]<< "\t";
    }
    cout << "\n";
}
void findsum(struct treeNode *pRoot,int sum,vector<int> &buffer,int level)
{
    if (pRoot == NULL) return ;//这个终止条件别忘写了
    int tmp = sum;
    int i = 0;
    buffer.push_back(pRoot->p_val);
    for (i = level;i >= 0;i--)
    {
        tmp -= buffer[i];
        if (tmp == 0) print(buffer,i,level);
    }
    vector<int> bufferl(buffer);//buffer1[0] = buffer[0],bufferl[1] = 新加入的节点的值....
    vector<int> bufferr(buffer);
    findsum(pRoot->pLeft,sum,bufferl,level+1);
    findsum(pRoot->pRight,sum,bufferr,level+1);
}
int main()
{
    int i = 0;
    int a[10];
    vector<int> vec;
    for (i = 0;i < 10;i++)
    {
        a[i] = i+1;
    }
    struct treeNode *pRoot = NULL;
    pRoot = createShortestTree(a,0,9);
    if (pRoot == NULL)
    {
        cout << "pRoot is null" << endl;
    }
    struct treeNode *new1 = (struct treeNode *)malloc(sizeof(struct treeNode));
    new1->p_val = 11;
    new1->pLeft = NULL;
    new1->pRight = NULL;
    struct treeNode *new2 = (struct treeNode *)malloc(sizeof(struct treeNode));
    new2->p_val = 4;
    new2->pLeft = NULL;
    new2->pRight = NULL;
    insetLastLeft(pRoot,new1);
    insertLastRight(pRoot,new2);
    findsum(pRoot,14,vec,0);
    return 0;
}

运行结果:
[root@localhost c++]# ./a.out
2       1       11
5       2       3       4
8       6
10      4