//给定二叉树和一个值，找到二叉树中和等于这个值的路径
#include <iostream>
#include<stack>
#include<vector>
using namespace std;
struct BinaryTreeNode{
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};

BinaryTreeNode* ContrustCore(int* startpreorder,int* endpreorder,int* startinorder,int* endinorder){
    //根据先序确定第一个数值确定根节点
   //BinaryTreeNode *root;
    int rootValue=startpreorder[0];
    BinaryTreeNode* root=new BinaryTreeNode();//为链表申请空间
    root->m_nValue=rootValue;
    root->m_pLeft=root->m_pRight=NULL;
    if(startpreorder==endpreorder){
        if(startinorder==endinorder && *startpreorder==*endpreorder)//z只有一个根节点
            return root;
        else
            throw std::exception();
    }
    //在中序找到根节点所在位置
    int*rootinoder=startinorder;
     while(rootinoder<=endinorder && *rootinoder!=rootValue)
        rootinoder++;
     if(rootinoder==endinorder && *rootinoder!=rootValue)//在中序中没有找到根节点
         throw exception();
     int leftLength=rootinoder-startinorder;
     int* leftPreorderEnd=startpreorder+leftLength;
     if(leftLength>0)//左子树的长度,构建左子树
     {
         root->m_pLeft=ContrustCore(startpreorder+1,leftPreorderEnd,startinorder,rootinoder-1);
     }
    if(leftLength<endpreorder-startpreorder)//存在右子树
        root->m_pRight=ContrustCore(leftPreorderEnd+1,endpreorder,rootinoder+1,endinorder);
    return root;
}
BinaryTreeNode* Contrust(int* preorder,int* inorder,int length){
        if(preorder==NULL||inorder==NULL||length<=0)
            return NULL;
        return ContrustCore(preorder,preorder+length-1,inorder,inorder+length-1);
}
void FindAllPath(BinaryTreeNode* pRoot,int expectedSum,vector<int>& path,int currentSum){
    currentSum+=pRoot->m_nValue;
    path.push_back(pRoot->m_nValue);
    bool isLeaf=(pRoot->m_pLeft==NULL)&&(pRoot->m_pRight==NULL);
    //叶子节点，并且路径上的节点的和等于期望的和
    if(currentSum==expectedSum && isLeaf){
        cout<<"the path is found:";
        vector<int>::iterator iter=path.begin();
        for(;iter!=path.end();iter++)
            cout<<*iter<<" ";
        cout<<endl;
    }
    //不是叶子节点，那就继续遍历左右子树
    if(pRoot->m_pLeft)
        FindAllPath(pRoot->m_pLeft,expectedSum,path,currentSum);
    if(pRoot->m_pRight)
        FindAllPath(pRoot->m_pRight,expectedSum,path,currentSum);
    //是叶子节点，但是路径的和并不等于期望的和,那就回退
    path.pop_back();
}
void FindPath(BinaryTreeNode* pRoot,int expectedSum){
    if(pRoot==NULL)
        return;
    vector<int> path;
    int currentSum=0;
    FindAllPath(pRoot,expectedSum,path,currentSum);
}
int main()
{
    BinaryTreeNode* Btree;
    int preorder[]={10,5,4,7,12};
    int inorder[]={4,5,7,10,12};
    Btree= Contrust(preorder,inorder,5);
    FindPath(Btree,22);
    return 0;
}