LeetCode 113.Path Sum II (路径总和 II)

痛定思痛。 2022-05-08 00:14 200阅读 0赞

题目描述：

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

**说明:** 叶子节点是指没有子节点的节点。

**示例:**  
给定如下二叉树，以及目标和 `sum = 22`，

5
                 / \
                4   8
               /   / \
              11  13  4
             /  \    / \
            7    2  5   1

返回:

[
       [5,4,11,2],
       [5,8,4,5]
    ]

--------------------

AC C++ Solution:

回溯法：

/* 回溯法 */
    class Solution {
    public:
        vector<vector<int>> pathSum(TreeNode* root, int sum) {
            vector<vector<int> > paths;
            vector<int> path;
            findPaths(root,sum,path,paths);
            return paths;
        }
        
    private:
        void findPaths(TreeNode* node, int sum, vector<int>& path, vector<vector<int> >& paths) {
            if(!node)   return;
            path.push_back(node->val);
            if(sum == node->val && node->left == NULL && node->right == NULL)
                paths.push_back(path);
            findPaths(node->left,sum-node->val,path,paths);
            findPaths(node->right,sum-node->val,path,paths);
            path.pop_back();
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，200人围观）

还没有评论，来说两句吧...

相关阅读

相关【LeetCode 113】路径总和 II

题目描述给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。说明: 叶子节点是指没有子节点的节点。示例: 给定如下二叉树，以

痛定思痛。/ 2022年12月04日 09:28/ 0 赞/ 127 阅读

相关 Path Sum II（C++路径总和 II）

（1）递归 / Definition for a binary tree node. struct TreeNode {

亦凉/ 2022年10月13日 05:13/ 0 赞/ 148 阅读

相关 Leetcode 113. 路径总和 II

题目重述给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。叶子节点是指没有子节点的

水深无声/ 2022年09月09日 13:42/ 0 赞/ 155 阅读

相关 leetcode 112. Path Sum, 113. Path Sum II | 112,113. 路径总和 I, II（Java）

题目 [https://leetcode.com/problems/path-sum/][https_leetcode.com_problems_path-sum]

超、凢脫俗/ 2022年09月03日 01:22/ 0 赞/ 167 阅读

相关 leetcode 113. Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals

谁借莪１个温暖的怀抱￠/ 2022年08月21日 02:22/ 0 赞/ 173 阅读

相关 LeetCode113—Path Sum II

LeetCode113—Path Sum II 原题 > Given a binary tree and a sum, find all root-to-leaf

悠悠/ 2022年07月26日 04:25/ 0 赞/ 164 阅读

相关 [Leetcode][python]Path Sum II/路径总和 II

题目大意将根到叶子的路径和为sum的路径都枚举出来。解题思路递归，并且用了python函数嵌套，有关函数嵌套可以看这一篇[文章][Link 1] 其实一开

落日映苍穹つ/ 2022年06月09日 23:18/ 0 赞/ 187 阅读

相关 LeetCode 113.Path Sum II (路径总和 II)

题目描述：给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。说明: 叶子节点是指没有子节点的节点。示例: 给定如下二叉树，以及

痛定思痛。/ 2022年05月08日 00:14/ 0 赞/ 201 阅读

相关【Leetcode】113. Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals

﹏ヽ暗。殇╰゛Y/ 2022年02月16日 06:31/ 0 赞/ 171 阅读

相关 leetcode 113. 路径总和 II

递归到叶子才将tans推进去ret ret.push\_back(tans); class Solution { public: vec

绝地灬酷狼/ 2022年02月12日 15:07/ 0 赞/ 180 阅读