LeetCode 113. 路径总和 II（回溯）

Michael阿明

发布于 2021-02-20 14:22:19

21000

代码可运行

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

运行总次数：0

代码可运行

1. 题目信息

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

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

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

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
返回:

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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/path-sum-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

类似题目LeetCode 112

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
         if(!root)
            return {};
        vector<vector<int>> ans;
        vector<int> way;
        path(root, 0, sum, way, ans);
        return ans;
    }
    void path(TreeNode *root, int cursum, int &sum, vector<int> way, vector<vector<int>> &ans)
    {
        if(!root)
            return;
        way.push_back(root->val);
        path(root->left, cursum+root->val, sum, way, ans);
        way.pop_back();
        way.push_back(root->val);
        path(root->right, cursum+root->val, sum, way, ans);
        if(!root->left && !root->right && cursum+root->val == sum)
        {
            ans.push_back(way);
        }
    }
};

《剑指Offer》同题：面试题34. 二叉树中和为某一值的路径

class Solution {
	vector<vector<int>> ans;
	vector<int> temp;
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        if(!root)
        	return {};
        dfs(root,sum,0);
        return ans;
    }

    void dfs(TreeNode* root, int& sum, int s)
    {
    	if(root && !root->left && !root->right)
    	{
    		if(s+root->val == sum)
    		{
    			temp.push_back(root->val);
    			ans.push_back(temp);
    			temp.pop_back();
    		}
    		return;
    	}
    	temp.push_back(root->val);
    	if(root->left)
    		dfs(root->left,sum,s+root->val);
    	if(root->right)
    		dfs(root->right,sum,s+root->val);
    	temp.pop_back();
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019/09/05 ，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树