《剑指offer》面试题25——二叉树中和为某一值的路径

题目描述：
输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

代码：

//主函数——核心代码
vector<vector<int> > allRes;
vector<int> tmp;
void bfsFind(TreeNode* node, int expectNumber)
{
        tmp.push_back(node->val);   //路径中保存当前结点的值
// cout<<"当前容器中的节点有：" <<endl;
// Print1Dvec(tmp);
        //判断是否为叶节点.若为叶节点且和为expectNumber，则保存路径
        if(node->left==NULL&&node->right==NULL&&(expectNumber-node->val)==0)
        {
            allRes.push_back(tmp);
        }
        else
        {
            if(node->left)
                bfsFind(node->left ,  expectNumber-node->val);
            if(node->right)
                bfsFind(node->right ,  expectNumber-node->val);
        }
        tmp.pop_back();    //删除当前结点，返回父结点。
}

vector<vector<int> > FindPath(TreeNode* root,int expectNumber)
{
    if(root!=NULL)
       bfsFind(root, expectNumber);
    return allRes;
}

int main()
{
        BinTree t;
        TreeNode* root=t.CreateTree();//创建二叉树

        cout<<"二叉树创建完毕..."<<endl;
        vector<int> myarray= PrintFromTopToBottom(root);
        Print1Dvec(myarray);

        vector<vector<int>> rout=FindPath(root , 22);
        cout<<"和为"<<"22的路径有："<<endl;
        Print2Dvec(rout);

        return 0;
}

运行结果：

二叉树创建完毕...
10  5  12  4  7
和为22的路径有：
10  5  7
10  12


Process returned 0 (0x0)   execution time : 0.271 s
Press any key to continue.

包含另外两个其他文件：bintree.h和bintree.cpp
其中，头文件bintree.h为：

#ifndef BINTREE_H_INCLUDED
#define BINTREE_H_INCLUDED

#include<iostream>
#include <vector>
#include<queue>
using namespace std;

struct  TreeNode
{
    int val;
    struct  TreeNode    *left;
    struct  TreeNode    *right;
    TreeNode(int x) :
        val(x), left(NULL), right(NULL) {}
};
class BinTree
{
public:
    TreeNode *root;
    TreeNode* CreateTree();
    void preOrder(TreeNode *r);//递归实现先序遍历
    void InOrder(TreeNode *r);//递归实现中序遍历
    void PostOrder(TreeNode *r);//递归实现后续遍历
};
void Print2Dvec(vector< vector<int> > &myvec);
vector<int> PrintFromTopToBottom(TreeNode* root);
void Print1Dvec(vector<int> &myarray);


#endif // BINTREE_H_INCLUDED

bintree.cpp 中函数定义为：

#include "bintree.h"

TreeNode* BinTree::CreateTree()
{
    TreeNode *p1=new TreeNode(10);
    TreeNode *p2=new TreeNode(5);
    TreeNode *p3=new TreeNode(12);
    TreeNode *p4=new TreeNode(4);
    TreeNode *p5=new TreeNode(7);
// TreeNode *p6=new TreeNode(6);
// TreeNode *p7=new TreeNode(7);
// TreeNode *p8=new TreeNode(8);
// TreeNode *p9=new TreeNode(9);
    p1->left=p2;
    p1->right=p3;
    p2->left=p4;
    p2->right=p5;
// p5->left=p6;
// p3->left=p7;
// p3->right=p8;
// p8->right=p9;
    root=p1;
    return root;
}


void Print2Dvec(vector< vector<int> > &myvec)
{
    if(myvec.size()==0)
        return;
    for(int i=0; i<myvec.size();i++)
    {
        for(int j=0;j<myvec[i].size();j++)
            cout<<myvec[i][j]<<" ";
        cout<<endl;
    }
    cout<<endl;
    return;
}

vector<int> PrintFromTopToBottom(TreeNode* root)
{
        vector<int> res;
        if(root==NULL)
            return res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
            {
                res.push_back(q.front()->val);
                if(q.front()->left!=NULL)
                    q.push(q.front()->left);
                if(q.front()->right!=NULL)
                    q.push(q.front()->right);
                q.pop();
            }
            return res;
}
void Print1Dvec(vector<int> &myarray)
{
    if(myarray.size()==0)
        cout<<"vector为空"<<endl;
    int num=myarray.size();
    for(int i=0; i<num;i++)
         cout<<myarray[i]<<" ";
    cout<<endl;
    return;
}