【剑指offer】_10二叉树和为某一路径值

题目描述

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

解题思路

要求一路径的和，那么必然终止条件为叶子结点，从根结点出发，从左往右，每条路径的和都与给定的值比较，自然能求出。
但往往二叉树的题，都会用到递归，本身是二叉树，那么子树必定为二叉树，如果找到规律？？
我们可以这样想，递归一次，旧调用系统栈一次保存数据。既然要路径上的所有结点的和等于给定的值，就说明给定的值减去路径的和等于0。我们就不难想到，每次递归减去当前根结点的值，一直到叶子结点，如果最后的值等于叶子结点的值那不就正好可以求解此题。
我们要考虑特殊情况，如果二叉树只有一个结点，并恰巧那个结点的值等于给定的值呢？？所以，每回减去当前根结点的值前，先判断是否相等，再减去。
如果到叶子结点不相等，那么就往上走，再往右边走。
有了上述思路，就不难写出如下代码

代码实现

class Solution {
    vector<vector<int>> result;
    vector<int>  path;
public:
    void find(TreeNode* root,int expectnum)
    {
        if(root == NULL)
            return ;
        path.push_back(root->val);
        if(!root->left&&!root->right&& expectnum == root->val)
            result.push_back(path);
        else
        {
            if(root->left)
                find(root->left,expectnum-root->val);
            if(root->right)
                find(root->right,expectnum-root->val);
        }
        path.pop_back();
    }
    
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        find(root,expectNumber);
        return result;
    }
};