题目描述

image.png

题解

解题思路与二叉树根节点到叶节点的所有路径和一题相似，都是采用递归算法。但这个题加了一点，要求保存路径到vector中。
为了保存路径，这里给递归函数传递一个vector类型的参数，用于保存从根节点到当前节点的路径。将当前节点值追加到vector末尾，再向下层传递。当到达叶节点时，判断是否符合条件，如果符合，就将该路径加到结果中。
到叶节点就可以完成判断并得到路径了，所以递归函数不需要返回值。

代码

// pathSum.cpp
#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int val){
        this->val = val;
        this->left = NULL;
        this->right = NULL;
    }
};

class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @param sum int整型
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > pathSum(TreeNode* root, int sum) {
        // write code here
        if (root == NULL){
            return meet;
        }
        vector<int> path;
        targetSum = sum;
        sumNumbers(root, root->val, path);
        return meet;
    }
private:
    vector<vector<int>> meet;
    int targetSum;
    void sumNumbers(TreeNode* t, int sum, vector<int> path){
        path.push_back(t->val);
        if (t->left == NULL && t->right == NULL){
            if (sum == targetSum){
                meet.push_back(path);
            }
        }
        if (t->left != NULL){
            sumNumbers(t->left, t->left->val + sum, path);
        }
        if (t->right != NULL){
            sumNumbers(t->right, t->right->val + sum, path);
        }
    }
};
int main()
{
    TreeNode* root = new TreeNode(5);
    TreeNode* left = new TreeNode(4);
    TreeNode* right = new TreeNode(8);
    TreeNode* leftleft = new TreeNode(1);
    TreeNode* leftright = new TreeNode(11);
    TreeNode* leftrightleft = new TreeNode(2);
    TreeNode* leftrightright = new TreeNode(7);
    TreeNode* rightright = new TreeNode(9);
    root->left = left;
    root->right = right;
    left->left = leftleft;
    left->right = leftright;
    leftright->left = leftrightleft;
    leftright->right = leftrightright;
    right->right = rightright;

    Solution s;
    vector<vector<int>> meet = s.pathSum(root, 22);
    for (int i = 0; i < meet.size(); i++){
        for (int j = 0; j < meet[i].size(); j++){

            cout << meet[i][j] << " ";
        }
        cout << endl;
    }
    delete root;
    delete left;
    delete right;
    delete leftleft;
    delete leftright;
    delete leftrightleft;
    delete leftrightright;
    delete rightright;
    return 0;

}