OJ-leetcode-113. 路径总和 II（中等二叉树）

缺乏、安全感 2022-12-10 14:48 152阅读 0赞

**目录**

题目

思路

代码

结果

优秀题解

提升笔记

全部代码

参考

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

# 题目 #

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

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

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

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

\[  
   \[5,4,11,2\],  
   \[5,8,4,5\]  
\]  
链接：https://leetcode-cn.com/problems/path-sum-ii

# 思路 #

自顶向下 回溯（vector去除点） 可剪枝递归

剪枝 sum<0

以上是我做题时记的简单思路，最后没有剪枝，提交代码前看了一下官方题解，发现可能有负数。

## 代码 ##

class Solution {
    	vector<vector<int>> path;
    	vector<int> nodes;
    public:
    	void pathSumHelper(TreeNode* root, int sum) {
    		if (root == NULL)return;
    		sum -= root->val;
    		nodes.emplace_back(root->val);
    		if (root->left == NULL&&root->right == NULL && 0 == sum)
    		{
    			path.emplace_back(nodes);
    			nodes.pop_back();
    			return;
    		}
    		// 剪枝  不行，有负数
    		//if (sum<0)return;
    		pathSumHelper(root->left,sum);
    		pathSumHelper(root->right, sum);
    		// 回溯
    		nodes.pop_back();
    	}
    	vector<vector<int>> pathSum(TreeNode* root, int sum) {
    		pathSumHelper(root, sum);
    		return path;
    	}
    };

## 结果 ##

![20200926223517586.PNG][] 结果

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70][] 递归栈

仅做演示步骤，并非真实递归栈，可使用栈模拟并输出。

# 优秀题解 #

递归中的题解没有找到太好的，看见了一个递归转循环的。

[后序遍历求递归路径][Link 1]

他模拟了栈，递归转为了循环，写的很不错，有时间总结一下递归转循环的。代码写的很好，push\_back改为emplace\_back就更好了。

# 提升笔记 #

1.递归剪枝

2.递归修改循环

# 全部代码 #

/*
    Project: 113.路径综合II
    Date:    2020/09/26
    Author:  Frank Yu
    */
    /**
    * Definition for a binary tree node.*/
    #define TElemType int
    #include<iostream>
    #include<vector>
    using namespace std;
    struct TreeNode {
       int val;
       TreeNode *left;
       TreeNode *right;
       TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     };
    //创建二叉树 规定数据域为-1，则为空 先序创建
    int InitTree(TreeNode* &T)
    {
    	TElemType a;
    	scanf("%d", &a);
    	if (-1 == a) T = NULL;
    	else {
    		T = new TreeNode(a);
    		//T->val = a;
    		InitTree(T->left);
    		InitTree(T->right);
    	}
    	return 0;
    }
    //这里就按照课本敲代码了，在对应功能实现函数进行逻辑判断
    void PreOrder(TreeNode* T)
    {
    	if (T != NULL)
    	{
    		printf("%d ", T->val);
    		PreOrder(T->left);//递归先序遍历左右子树
    		PreOrder(T->right);
    	}
    }
    //调用InitTree
    void CreateBiTree(TreeNode* &T)
    {
    	printf("请按照先序遍历输入二叉树(-1无):");
    	InitTree(T);
    	printf("二叉树先序遍历序列:");
    	PreOrder(T);
    	printf("\n");
    }
    class Solution {
    	vector<vector<int>> path;
    	vector<int> nodes;
    public:
    	void pathSumHelper(TreeNode* root, int sum) {
    		if (root == NULL)return;
    		//cout << root->val << endl;
    		//cout << sum << endl;
    		//for (auto node : nodes)
    		//{
    		//	cout << node;
    		//}
    		//cout << endl;
    		sum -= root->val;
    		nodes.emplace_back(root->val);
    		if (root->left == NULL&&root->right == NULL && 0 == sum)
    		{
    			path.emplace_back(nodes);
    			nodes.pop_back();
    			return;
    		}
    		// 剪枝  不行，有负数
    		//if (sum<0)return;
    		pathSumHelper(root->left,sum);
    		pathSumHelper(root->right, sum);
    		// 回溯
    		nodes.pop_back();
    	}
    	vector<vector<int>> pathSum(TreeNode* root, int sum) {
    		pathSumHelper(root, sum);
    		return path;
    	}
    };
    
    int main()
    {
    	TreeNode * root = NULL;
    	CreateBiTree(root);
    	Solution s;
    	auto paths = s.pathSum(root,22);
    	for (auto v : paths)
    	{
    		for (auto node:v)
    		{
    			cout << node;
    		}
    		cout << endl;
    	}
    	return 0;
    }

# 参考 #

[二叉树基本操作函数（先、中、后、层次遍历，含全部代码）][Link 2]

更多内容：[OJ网站题目分类，分难度整理笔记（leetcode、牛客网）][OJ_leetcode]

喜欢本文的请动动小手点个赞，收藏一下，有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。如果您感觉有所收获，自愿打赏，可选择支付宝18833895206（小于），您的支持是我不断更新的动力。

[20200926223517586.PNG]: /images/20221123/fbc50a2723c049df8e8a56b49d3c30ef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70]: /images/20221123/4610c08956464dc787fe8003dc48ad7f.png
[Link 1]: https://leetcode-cn.com/problems/path-sum-ii/solution/
[Link 2]: https://blog.csdn.net/lady_killer9/article/details/86377635
[OJ_leetcode]: https://blog.csdn.net/lady_killer9/article/details/108273799