leetcode 113. 路径总和 II

题目详情

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。 说明: 叶子节点是指没有子节点的节点。 示例: 给定如下二叉树，以及目标和 sum = 22， 5 / 4 8 / / 11 13 4 / / 7 2 5 1 返回: [ [5,4,11,2], [5,8,4,5] ]

我的代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
          
   
private:
    vector<vector<int>> paths;
    vector<int> path;
public:
    inline void findPath(TreeNode* root, int sum) {
          
   
        sum -= root->val;
        path.push_back(root->val);
        if (sum == 0 && !root->left && !root->right) {
          
   
            paths.push_back(path);
            return;
        }
        if (root->left) {
          
   
            findPath(root->left, sum);
            path.pop_back();
        }
        if (root->right) {
          
   
            findPath(root->right, sum);
            path.pop_back();
        }
    }

    inline vector<vector<int>> pathSum(TreeNode* root, int sum) {
          
   
        if (!root) {
          
   
            return {
          
   };
        }
        findPath(root, sum);
        return paths;
    }
};

我的成绩

执行结果：通过 执行用时：8 ms, 在所有 C++ 提交中击败了92.35%的用户 内存消耗：16.5 MB, 在所有 C++ 提交中击败了75.58%的用户

一些想法

递归查询即可。

执行用时为 0 ms 的范例

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
          
   
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) 
    {
          
   
        vector<vector<int>> res;;
        vector<int> temp;
        help(root, 0, sum, temp, res);
        return res;
    }
    void help(TreeNode* now_node, int now_sum, int target_sum, vector<int>& temp, vector<vector<int>>& res)
    {
          
   
        if(!now_node) return;
        now_sum += now_node->val;
        temp.push_back(now_node->val);
        if(!now_node->left && !now_node->right && now_sum == target_sum)
        {
          
   
            res.push_back(temp);
            temp.pop_back();
            return;
        }
        if(now_node->left)
            help(now_node->left, now_sum, target_sum, temp, res);
        if(now_node->right)
            help(now_node->right, now_sum, target_sum, temp, res);
        temp.pop_back();
    }   
};

思考

参见