二叉树中和为某一值的路径

题目描述

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

 

解:这题其实有限制条件，但是没看出来。就是要从根节点一直到叶子节点，全部的和。中间的节点不会断层，其实就是深度优先遍历的类型

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    void ResFindPath(vector<vector<int> >&vec_vec,vector<int>vec,TreeNode* root,int expectNumber)
    {

        if(root==nullptr)
        {
            return;
        }
                //不计算本节点值
        //ResFindPath(vec_vec,vec,root->right,expectNumber);
        //ResFindPath(vec_vec,vec,root->right,expectNumber);
        
        //计算本节点值
        vec.emplace_back(root->val);
        if(expectNumber-root->val==0&&(root->left==nullptr&&root->right==nullptr))
        {
            vec_vec.emplace_back(vec);
            return;
        }
        ResFindPath(vec_vec,vec,root->left,expectNumber-root->val);
        ResFindPath(vec_vec,vec,root->right,expectNumber-root->val);
    }
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int> > vec_vec_ret;
        vector<int> vec;
        ResFindPath(vec_vec_ret,vec,root,expectNumber);
        return vec_vec_ret;
    }
};