题目描述

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

叶子节点 是指没有子节点的节点。

image.png

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

这个题确实要找到答案必不可少的是走完路径然后知道路径和是多少，所以需要遍历一遍所有的节点
但是需要保存路径上的节点，所以需要用类似八皇后那种回溯法来做。

好像也没太好的优化思路了

代码：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     int tmp_sum=0;
  15.     vector<vector<int>> ans;
  16.     vector<int> tmp_path;
  17.     void DFS(TreeNode* root,int target){
  18.         if(root->right==nullptr&&root->left==nullptr){
  19.             //说明是叶子节点
  20.             tmp_sum = tmp_sum+root->val;
  21.             tmp_path.push_back(root->val);
  22.             if(tmp_sum == target){
  23.                 ans.push_back(tmp_path);
  24.             }
  25.             tmp_sum = tmp_sum-root->val;
  26.             tmp_path.pop_back();
  27.             return;
  28.         } 
  29.         tmp_sum += root->val;
  30.         tmp_path.push_back(root->val);
  31.         if(root->left!=nullptr) DFS(root->left,target);
  32.         if(root->right!=nullptr) DFS(root->right,target);
  33.         tmp_path.pop_back();
  34.         tmp_sum -=root->val;
  35.     }
  36.     vector<vector<int>> pathSum(TreeNode* root, int target) {
  37.         if(root==nullptr) return ans;
  38.         DFS(root,target);
  39.         return ans;
  40.     }
  41. };

复杂度分析

时间复杂度：遍历节点的话，其实N要是算二叉树节点的个数的话就是O(N)
空间复杂度: 也是O（N）