题解 | #二叉树根节点到叶子节点和为指定值的路径#

/*
描述
给定一个二叉树和一个值\ sum sum，请找出所有的根节点到叶子节点的节点值之和等于\ sum sum 的路径，
例如：
给出如下的二叉树，\ sum=22 sum=22，返回 [[5,4,11,2],[5,8,9]]
Main idea:
使用一个vector (path)保存当前路径，然后使用先序遍历，先将当前节点值push进path
若当前节点为叶子节点且此前路径的sum+当前节点的值==target_sum，则将path储存进result；
若不是，则无需储存
遍历完左右子树后将节点的值pop出path，使得祖先节点遍历另一分支可以产生新的path
*/

class Solution {
public:
    vector<vector<int> > pathSum(TreeNode* root, int sum) {
        if (root == nullptr)
            return result;
        target_sum = sum;
        preOrder(root, 0);
        return result;
    }
private:
    int target_sum;
    vector<int> path;
    vector<vector<int> > result;
    void preOrder(TreeNode* root, int sum) {
        path.push_back(root->val);
        if (root->left == nullptr && root->right == nullptr) {
            // leaf node
            if (sum + root->val == target_sum)
                result.push_back(path);
        }
        else{
            // not the leaf node
            if (root->left)
                preOrder(root->left, sum + root->val);
            if (root->right)
                preOrder(root->right, sum + root->val);
        }
        path.pop_back();
    }
};