面试题25：二叉树中和为某一值的路径

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

struct BinaryTreeNode{
    int value;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
    BinaryTreeNode(int data=int()):value(data),left(NULL),right(NULL)
    {}
};

分析

既然题目要求要打印二叉树上的所有节点，就需要遍历该二叉树。而在最常见的前、中、后序三种遍历方式中，只有前序遍历能第一个访问二叉树的根节点，也就是先累加根节点的值。所以可以在前序遍历的过程中计算当前路径上所以节点的和。如果当前节点是叶子节点且和等于给定的整数，就打印出当前路径上的节点。否则就将该叶子节点从路径上删除。由此可见，我们需要一个数组来保存当前的路径。

代码如下：

void _FindPath(BinaryTreeNode* root,int sum,vector<int>& v,int cursum)
{
    if(root==NULL)
        return;
    cursum+=root->value;
    v.push_back(root->value);
    if(cursum==sum && root->left==NULL && root->right==NULL)
    {
        vector<int>::iterator iter=v.begin();
        for(;iter!=v.end();++iter)
        {
            cout<<*iter<<" ";
        }
        cout<<endl;
    }
    else
    {
        _FindPath(root->left,sum,v,cursum);
        _FindPath(root->right,sum,v,cursum);
    }
    v.pop_back();
    return;
}

void FindPath(BinaryTreeNode* root,int sum)
{
    vector<int> v;
    _FindPath(root,sum,v,0);
}

以上

如果你有任何想法或是可以改进的地方，欢迎和我交流！

完整代码及测试用例在github上：点我前往