【剑指offer】二叉树中和为某一值的路径，C++实现

原创文章，转载请注明出处！

博客文章索引地址

1.题目

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径由结点和有向边组成，从根结点到叶节点。

// 二叉树结点的定义

struct BinaryTreeNode

{

      int val;

      BinaryTreeNode *left;

      BinaryTreeNode *right;

}

      举例：

二叉树中有两条和为22的路径：{10,5,7}和{10,12}

2.思路

本题使用前序遍历的方式访问节点，使用二维向量result存储全部路径，使用一维向量tmp存储当前路径。遍历二叉树的过程：按前序遍历顺序访问每一个节点。访问每个结点时，将结点添加到路径向量tmp中。如果当前结点是叶子结点，则判断当前路径是否是符合条件的路径，符合条件的路径存入到二维向量result；如果当前结点不是叶子结点，则递归当前节点的左右子节点。举例：

3.代码

class Solution {

public:

    vector<vector<int> > FindPath(TreeNode* root,int expectNumber)

    {

        if(root) dfsFind(root, expectNumber);

        return allRes;

    }

    void dfsFind(TreeNode * node , int target)

    {

        tmp.push_back(node->val);

        if(!node->left && !node->right)

        {

            if(target - node->val == 0)

                allRes.push_back(tmp);

        }

        else

        {

            if(node->left) dfsFind(node->left, target - node->val);

            if(node->right) dfsFind(node->right, target - node->val);

        }

        if(!tmp.empty())

            tmp.pop_back();

    }

private:

    vector<vector<int> >allRes;

    vector<int> tmp;

};

4.测试用例

• 空指针
• 二叉树中没有符合条件的路径
• 二叉树中有一条符合条件的路径
• 二叉树中有多条符合条件的路径